سوال ۲۰
می‌خواهیم تعدادی مهره‌ی $2\times 1$ را در یک جدول $12\times 1$ بچینیم به‌طوری‌که هر مهره دقیقاً روی دو خانه‌ی مجاور قرار گیرد و دیگر نتوانیم هیچ مهره‌یی روی جدول قرار دهیم. به چند طریق این کار ممکن است؟
- ۱۹
- ۲۰
- ۲۱
- ۲۲
- ۲۳
پاسخ
گزینه (۳) درست است.
راه‌حل اول: اگر تعداد مهره‌ها ۶ عدد باشد آن‌گاه به یک طریق می‌توان آن‌ها را چید.
اگر تعداد مهره‌ها ۵ عدد باشد٬ آن‌گاه دو خانه‌ی غیر مجاور باید خالی بمانند که به یکی از ۱۵ طریق زیر ممکن است:
$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)$ برابر با ۲۱ به‌دست می‌آید.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
