====== سوال ۸ ======



هیربد و هیراد روی نقاط سمت چپ یک شبکه‌ی
$3 \times 8$
ایستاده‌اند و خانه‌های آن‌ها در نقاط سمت راست جدول قرار دارد.

{{ :سوالات_المپیاد:مرحله_ی_دوم:دوره_ی_۳۰:capture4.png |}}

هر یک از آنها در هر گام می‌تواند به یکی از نقاط مجاور راستی، بالایی و یا پایینی‌اش (در صورت وجود) که قبلا از آن عبور نکرده، وارد شود.\\
این دو نفر قصد دارند به خانه‌هایشان بروند و متاسفانه امروز با هم قهر کرده‌اند؛ برای همین می‌خواهند طوری به خانه‌هایشان بروند که مسیرهای حرکتشان هیچ نقطه و یال مشترکی نداشته باشند. هیربد و هیراد به چند طریق می‌توانند مسیرهایشان را انتخاب کنند؟




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


{{ :سوالات_المپیاد:مرحله_ی_دوم:دوره_ی_۳۰:untitled2.png |}}
</پاسخ>


  * [[سوال ۷|سوال قبل]]
  * [[سوال ۹|سوال بعد]]