سوال ۸
هیربد و هیراد روی نقاط سمت چپ یک شبکه‌ی $3 \times 8$ ایستاده‌اند و خانه‌های آنها در نقاط سمت راست جدول قرار دارد.
هر یک از آنها در هر گام می‌تواند به یکی از نقاط مجاور راستی، بالایی و یا پایینی‌اش (در صورت وجود) که قبلا از آن عبور نکرده، وارد شود.
این دو نفر قصد دارند به خانه‌هایشان بروند و متاسفانه امروز با هم قهر کرده‌اند؛ برای همین می‌خواهند طوری به خانه‌هایشان بروند که مسیرهای حرکتشان هیچ نقطه و یال مشترکی نداشته باشند. هیربد و هیراد به چند طریق می‌توانند مسیرهایشان را انتخاب کنند؟
- 577
- 239
- 1393
- 171
- 729
پاسخ
گزینه (۱) درست است.
$f(n)$ را تعداد جفت مسیرهای مستقل از هم در یک شبکه $3 \times n$ از بالا چپ به بالا راست و از پایین چپ به پایین راست می‌نامیم.
$g(n)$ را تعداد جفت مسیرهای مستقل از هم در یک شبکه $3 \times n$ از بالا چپ به بالا راست و از وسط چپ به پایین راست می‌نامیم.
واضح است که جواب مسئله $f(8)$ می‌باشد. همچنین روابط زیر بین $f$ و $g$ برقرار است و می‌توان جدول را مطابق با روابط پر کرد.
- $f(n) = f(n-1) + 2g(n-1)$
- $g(n) = f(n-1) + g(n-1)$
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
