====== سوال ۲۰ ======

می‌خواهیم تعدادی مهره‌ی ‎$2\times 1$‎ را در یک جدول
‎$12\times 1$‎ بچینیم به‌طوری‌که هر مهره دقیقاً روی دو خانه‌ی مجاور قرار گیرد و دیگر نتوانیم هیچ مهره‌یی روی جدول قرار دهیم. به چند طریق این کار ممکن است؟


  - ‎۱۹
  - ۲۰
  - ۲۱
  - ۲۲
  - ۲۳‎

<پاسخ>
گزینه (۳) درست است.


**راه‌حل اول:** اگر تعداد مهره‌ها ۶ عدد باشد آن‌گاه به یک طریق می‌توان آن‌ها را چید.

اگر تعداد مهره‌ها ۵ عدد باشد٬ آن‌گاه دو خانه‌ی غیر مجاور باید خالی بمانند که به یکی از ۱۵ طریق زیر ممکن است:

<WRAP :en>
$1-4 \quad \quad \quad 3-6 \quad \quad \quad 5-8 \quad \quad \quad 7-10 \quad \quad \quad 9-12 \\ 1-6 \quad \quad \quad 3-8 \quad \quad \quad 5-10 \quad \quad \quad 7-12 \\ 1-8 \quad \quad \quad 3-10 \quad \quad \quad 5-12 \\ 1-10\quad\quad\quad3-12 \\ 1-12$ 
</WRAP>
اگر تعداد مهره‌ها ۴ عدد بیش‌تر باشد آن‌گاه چهار خانه‌ی غیر مجاور باید خالی بمانند که به یکی از ۵ طریق زیر ممکن است.


$$1-4-7-10 \\ 1-4-7-12 \\ 1-4-9-12 \\ 1-6-9-12 \\ 3-6-9-12$$


مجموع کل حالات مورد اشاره برابر $1+15+5$؛ یعنی ۲۱ می‌باشد.

**راه حل دوم:** تعداد  طرق چیدن مهره‌های $2\times1$ در جدول $n\times1$ را $f_n$ می‌نامیم. هریک از $f_n$ طریق دو حالت می‌تواند داشته باشد. به این صورت که یا خانه‌ی $n$ ام آن خالی یا پر است. در حالت او ل خانه‌های $(n-1)$ ام و $(n-2)$ ام یقینا پر هستند و از آن خانه به قبل نیز تعداد طرق چیدن‌ها برابر $f_{n-3}$ می‌باشد. در حالت دوم نیز خانه‌ی $(n-1)$ ام یقینا پر هست٬ بنابراین تعداد طرق چیدن مهره در سایر خانه‌ها برابر $f_{n-2}$ می‌باشد٬ یعنی رابطه‌ی $f_n=f_{n-2}+f_{n-3}$ برقرار است. چون $f(2)=1 ، f(1)=1$ و $f(3)=2$، بنابراین با محاسبه‌٬ $f(12)$ برابر با ۲۱ به‌دست می‌آید.


</پاسخ>
  * [[سوال ۲۱|سوال بعد]]
  * [[سوال ۱۹|سوال قبل]]