Processing math: 100%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۵:ترکیبیات:سوال ۵

روزبه گرمشه

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

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

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

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

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

ثابت کنید تعداد روش‌های متفاوت رسیدن روزبه به نقطه‌ی (n,k) برابر (2nnk) است.


ابزار صفحه