المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۷:سوال ۱۳

سوال ۱۳

یک جوجه در گوشه‌ی پایین و سمت چپ مستطیلی به طول ۹۹ و عرض ۵۹ قرار گرفته است. این جوجه می‌خواهد با تعدادی «حرکت»، خود را به گوشه‌ی بالا سمت راست این مستطیل برساند. جوجه در هر حرکت می‌تواند به اندازه‌ی توانی از ۲ (یعنی ۱ یا ۲ یا ۴ یا… واحد) به سمت راست یا بالا حرکت کند، به شرط آن که از جدول خارج نشود. او به چند طریق می‌تواند به مقصد برسد به طوری که کمترین تعداد «حرکت» را انجام داده باشد؟

  1. ۵۷۶۰
  2. ۱۲۶
  3. ۲۸۸۰
  4. ۳۶۲۸۸۰
  5. هیچ‌کدام

پاسخ

گزینه‌ی (۴) درست است.

این جوجه در صورتی کم‌ترین تعداد حرکت را خواهد داشت که حرکت تکراری انجام ندهد. زیرا در صورت تکرار به جای این‌که یک‌بار از دو برابر آن عدد که جز انتخاب‌هایش نیز بوده است استفاده کند دوبار از آن عدد استفاده کرده است. در نتیجه باید از حرکتهای زیر استفاده کند:

$99 = 64 + 32 + 2 + 1$

$59 = 32 + 16 + 8 + 2 + 1$

اگر اندازه حرکات یکسان بود به تعداد $\binom{9}{4}$ انتخاب برای رسیدن به نقطه نهایی داشتیم. چون همه حرکات یکسان نیستند این عدد باید مقدار زیر باشد:

$\binom{9}{4}×5!×4!=362880$


ابزار صفحه