Processing math: 100%

سوال ۲۰

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

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

پاسخ

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

تعداد روش‌های رسیدن از خانه‌ی پایین-چپ به خانه‌ی بالا-راست در یک جدول 2×n را an و تعداد روش‌های رسیدن از خانه‌ی بالا-چپ به خانه‌ی بالا-راست در همین جدول را bn در نظر می‌گیریم. با حالت‌بندی روی گام نخست، روابط بازگشتی زیر را داریم: an=2an1+2bn1+2an2+2bn2bn=2an1+2bn1+2an2+2bn2 از آن‌جایی که a1=1a2=5b1=1b2=5 مقدار a5=560 به دست می‌آید.