روزبه گرمشه

روزبه پس از طرح سوال دو مرحله دوم، با تصمیم قاضی به سرزمینی دور تبعید شد. این سرزمین مانند یک صفحه‌ی مختصات است. روزبه در نقطه‌ی $(0, 0)$ این سرزمین سکونت دارد. هوا به تازگی در این نقطه بسیار گرم شده است و روزبه از هوای گرم متنفر است؛ پس تصمیم دارد به نقطه‌ی $(n, k)$ برود که شنیده است نقطه‌ی نسبتن سردی است! روزبه در هر مرحله می‌تواند از یکی از وسایل نقلیه‌ی این سرزمین (شتر، گاو، خر و قاطر) استفاده کند. این وسایل نقلیه به شکل زیر کار می‌کنند:

• اگر روزبه در نقطه‌ی $(i, j)$ باشد، شتر او را به نقطه‌ی $(i+1, j-1)$ می‌برد.
• اگر روزبه در نقطه‌ی $(i, j)$ باشد، گاو او را به نقطه‌ی $(i+1, j+1)$ می‌برد.
• اگر روزبه در نقطه‌ی $(i, j)$ باشد، خر او را به نقطه‌ی $(i+1, j)$ می‌برد.
• قاطر نیز مانند خر عمل می‌کند.

واضح است که کار روزبه در دقیقن $n$ مرحله انجام می‌شود. این سرزمین از نظر حمل و نقل قوی است؛ پس در هر مرحله تمام وسایل نقلیه در دست‌رس هستند!

دو روش برای رسیدن به نقطه‌ی $(n, k)$ را متفاوت گوییم؛ هرگاه حداقل یکی از دو شرط زیر برقرار باشد:

• مرحله‌ای مانند $L$ وجود داشته باشد که مکان روزبه پس از آن مرحله در دو روش، متفاوت باشد.
• مرحله‌ای مانند $L$ وجود داشته باشد که وسیله‌ی نقلیه‌ی مورد استفاده‌ی روزبه در آن مرحله در دو روش، متفاوت باشد.

ثابت کنید تعداد روش‌های متفاوت رسیدن روزبه به نقطه‌ی $(n, k)$ برابر $\binom{2n}{n-k}$ است.

• سوال بعد
• سوال قبل