سوال ترکیبیات جالب!

[Goharshady]

با یک تناظر یک به یک ، نشان دهید تعداد حالات حرکت در شبکه ای(r×(n-1 از گوشه پایین سمت چپ به گوشه بالا سمت راست برابر است با تعداد جوابهای صحیح نامنفی معادله ی زیر:

[center:75c08f21b3]

[/center:75c08f21b3]

 

[Olympiad]

خوب ،‌ حركت روبه بالا را با 0 و حركت رو به راست هم با 1 نمايش ميدهيم . ( البته بايد ذكر ميكرديد كه نزديكترين مسير ) بنابر اين دنباله اي در مبناي 2 به طول

ميخواهيم كه شامل

تا 1 و

تا 1 باشد كه اين تعداد دنباله برابر

است .
تعداد جواب هاي نا منفي معادله ي

هم برابر

( با تناظر ثابت ميشه )
بنابر اين...

 

[Goharshady]

وقتی می گیم با تناظر یک به یک حل کنید یعنی بین تعداد جوابهای معادله و تعداد راهها (به قول شما نزدیکترین راهها) تناظر برقرار کنید نه این که بین هرکدام از آنها و دنباله ای از صفرها و یکها!
مستقیما تناظر یک به یک برقرار کنید. اگر قرار بود این کار را نکنیم صرفا می گفتیم تعداد حالات برابر است پس تناظر یک به یک وجود دارد!!!!

 

[Olympiad]

به ازاي هر يك راه كه از يك و صفر تشكيل شده ، يك جواب از آن معادله را در اختيار داريم

 

[Olympiad]

درسته ديگه مگه نه ؟!؟!؟!

 

[Goharshady]

نمی دونم چه جوری بگم!

ببین شما داری اول بین a و b تناظر یک به یک ایجاد می کنی ، بعد بین b و c بعد نتیجه می گیری که بین a و c تناظر یک به یک هست. با این حساب میشه 2 تا تناظر یک به یک.
سوال یک تناظر یک به یک می خواهد.
یعنی مستقیما تعداد جوابهای معادله را به راههای مسیر مرتبط کنید.
ممکنه فکر کنی خیلی سوال مزخرفیه که همچین چیزی می خواهد ولی حقیقت اینه که واقعا نکته ی جالبی در این بین هست.

 

[Fardad]

تعداد حرکات عمودی r است . تعداد خانه های افقی هم n-1 تاست ، هر حالت در شبکه ، x1 برابر تعداد حرکات عمودی در ضلع یک ستون یک و x2 ضلع 2 ستون 1 یا ضلع یک ستون 2 و x3 ضلع 2 ستون 3 و ... و xn ضلع 2 ستون n-1 یا ضلع 2 ستون n است !
توضیحش خیلی سخته ...
امیدوارم با همه سختی ای که در تصویر این سوال کشیدم راهم درست باشه !!

 

[Olympiad]

تعداد حرکات عمودی r است . تعداد خانه های افقی هم n-1 تاست ، هر حالت در شبکه ، x1 برابر تعداد حرکات عمودی در ضلع یک ستون یک و x2 ضلع 2 ستون 1 یا ضلع یک ستون 2 و x3 ضلع 2 ستون 3 و ... و xn ضلع 2 ستون n-1 یا ضلع 2 ستون n است !
توضیحش خیلی سخته ...
امیدوارم با همه سختی ای که در تصویر این سوال کشیدم راهم درست باشه !!

منظور من هم منظور ايشون بود .
گفتم به ازاي هر راه كه از يك و ضفر تشكيل شده يك جواب از معادله را نسبت ميدهيم
يعني 1 ها را در دنباله به عنوان جدا كننده در نظر ميگيريم : X1 تعداد صفرها تا لولين عدد 1 ، x2 = تعداد صفرها بين اولين 1 و دومين يك و...