سوالات المپیاد:مرحله ی اول:دوره ی ۱۹:سوال ۲۵
سوال ۲۵
یک حشره در خانه‌ی گوشه‌ي پایین و سمت چپ یک مربع ۷×۷ نشسته است. در هر جهش یکی از سه کار زیر را انجام می‌دهد:
- دو واحد به سمت راست می‌پرد٬
- دو واحد به سمت بالا می‌پرد٬ یا
- با یک پرش ۴۵ درجه‌ای٬ یک واحد به سمت راست و یک واحد به سمت بالا می‌پرد.
دقت کنید که این حشره با دقیقا ۶ جهش به خانه‌ی گوشه‌ی بالا سمت راست مربع می‌رسد. تعداد دنباله‌های مختلف جهش که حشره را به خانه‌ي گوشه‌ی بالا سمت راست مربع می‌رسانند چندتاست؟
- ۳۶
- ۶۴
- ۲۷۶
- ۱۰۱
- ۱۴۱
پاسخ
گزینه‌ی (۵) درست است.
تنها شرطی که در این دنباله‌ی به طول ۶ داریم این است که تعداد حرکات شماره‌ی یک و دو باهم برابر باشند.
در نتیجه تعداد حالات ممکن در صورتی که تعداد حرکات شماره‌ی یک بین صفر تا سه باشد به ترتیب برابر است با: \binom{6}{3}, \binom{6}{2,2,2}, \binom{6}{1,1,4}, \binom{6}{6} که جمع این اعداد برابر می‌شود با ۱۴۱.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
