سوال ۲۰

در سوال قبل، به چند طریق می‌توانیم مهره را از خانه‌ی پایین-چپ به خانه‌ی بالا-راست برسانیم، طوری که از هر خانه حداکثر یک بار عبور کنیم؟

  1. ۱۰۰
  2. ۱۱۶
  3. ۵۶۰
  4. ۴۶۴
  5. ۴۸۰

پاسخ

گزینه‌ی ۳ درست است.

تعداد روش‌های رسیدن از خانه‌ی پایین-چپ به خانه‌ی بالا-راست در یک جدول $2 \times n$ را $a_n$ و تعداد روش‌های رسیدن از خانه‌ی بالا-چپ به خانه‌ی بالا-راست در همین جدول را $b_n$ در نظر می‌گیریم. با حالت‌بندی روی گام نخست، روابط بازگشتی زیر را داریم: \begin{align*} a_n&=2a_{n-1}+2b_{n-1}+2a_{n-2}+2b_{n-2}\\ b_n&=2a_{n-1}+2b_{n-1}+2a_{n-2}+2b_{n-2}\\ \end{align*} از آن‌جایی که $$a_1 = 1 \qquad a_2 = 5 \qquad b_1 = 1 \qquad b_2 = 5$$ مقدار $a_5 = 560$ به دست می‌آید.