سوال ۲۰

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

  1. ‎۱۹
  2. ۲۰
  3. ۲۱
  4. ۲۲
  5. ۲۳‎

پاسخ

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

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

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

$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$

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

$$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)$ برابر با ۲۱ به‌دست می‌آید.