======سوال ۱۵======

شکل زیر نواری از خانه‌ها را نشان می‌دهد که تعدادی از آن‌ها سیاه شده‌اند. مهره‌ای از خانه‌ی ابتدای سمت چپ نوار شروع به حرکت می‌کند و در هر گام به اندازه‌ی یک یا دو خانه به جلو می‌جهد٬ به شرطی که خانه‌ي مقصد سیاه نباشد. 

مهره به چند طریق می‌تواند به انتهای نوار برسد؟

{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۱۹:x.png?nolink |}}

  - ۱۲۰
  - ۱۳۰
  - ۱۴۰
  - ۱۵۰
  - ۱۶۰
<پاسخ>
گزینه‌ی (5) درست است.


درصورتی که هیچ خانه‌ای سیاه نباشد تعداد روش‌های رسیدن به خانه‌ی آخر از رابطه‌ی بازگشتی زیر تبعیت می‌کند:


$f_n=f_{n-1}+f_{n-2} f_1=f_2=1$


برای اثبات این ادعا کافیست حرکت نهایی را در نظر بگیریم. حرکت نهایی پرش به طول یک یا دو است که هرکدام از جملات بالا را می‌سازد.


از طرفی وقتی یک خانه‌ی سیاه وجود داشته باشد باید در آن حرکت دو خانه پرید. پس جواب مسئله را می‌توان به حاصل‌ضرب قسمت‌هایی که خانه‌ی سیاه ندارند تجزیه کرد.در نتیجه جواب مسئله برابر است با$f_5×f_3×f_6×f_3$ که برابر با ۱۶۰ است.

</پاسخ>



  * [[سوال ۱۶|سوال بعد]]
  * [[سوال ۱۴|سوال قبل]]