سؤال ۳۰
آقای ملکی می‌خواهد از سه نردبان ۷ پله‌ای هواپیما که مانند شکل مقابل در کنار هم قرار دارند بالا برود و در بالاترین سطح قرار بگیرد. او در هر حرکت می‌تواند به یک پله بالاتر دریکی از نردبان‌های مجاور یا نردبانی که اکنون بر روی آن قرار دارد برود، ولی نمی‌تواند در یک حرکت از نردبان اول به نردبان سوم یا برعکس برود. اگر او در ابتدا بر روی اولین پله نردبان سمت راست باشد، به چند طریق می‌تواند خود را به یکی از پله‌های هفتم برساند؟
- ۷۰
- ۱۲۸
- ۱۶۹
- ۱۸۲
- ۲۳۹
پاسخ
گزینه (۳) درست است.
حرکت بر روی سه نردبان از سمت راست به چپ را به ترتیب با $a$ ، $b$ و $c$ نمایش می‌دهیم. هدف مسئله نوشتن دنباله‌این ۷ حرفی با استفاده از سه حرف $a$ ، $b$ و $c$ می‌باشد به‌طوری که شروع دنباله با حرف $a$ و نیز هیچ $a$ و $c$ای مجاور نباشند.
اگر تعداد دنباله‌های موجود در مرحله‌ی $i$ام برابر $x_i$ در نظر بگیریم به طوری که $a_i$ تا از آن‌ها ختم به a،$b_i$ تا از آن‌ها ختم به $b$ و بالاخره $c_i$ تا از آن‌ها ختم به $c$ باشند٬ آن‌گاه در مرحله بعدی به ازای هر دنباله‌ای که به $b$ ختم می‌شود٬ ۳ دنباله جدید ونیز به ازای هر دنباله‌ای که به $a$ و یا $c$ ختم می‌شود ۲ دنباله جدید می‌توان نوشت٬ بنابراین:
$\left. \begin{array}{l l l}a_{i+1}=a_i+b_i\\c_{i+1}=c_i+b_i\\b_{i+1}=a_i+b_i+c_i\end{array} \right\}$ $\Rightarrow x_{i+1}=2(a_i+b_i+c_i)+b_i=2x_i+b_i$
جدول $a_i$٬$b_i$٬$c_i$ و $x_i$ به ازای $i$ از ۱ تا ۸ در جدول زیر آمده است:
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
