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