سوال ۲۰
در سوال قبل، به چند طریق میتوانیم مهره را از خانهی پایین-چپ به خانهی بالا-راست برسانیم، طوری که از هر خانه حداکثر یک بار عبور کنیم؟
- ۱۰۰
- ۱۱۶
- ۵۶۰
- ۴۶۴
- ۴۸۰
پاسخ
گزینهی ۳ درست است.
تعداد روشهای رسیدن از خانهی پایین-چپ به خانهی بالا-راست در یک جدول
$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$
به دست میآید.
| ▸ سوال قبل | سوال بعد ◂ |