====== سوال ۲۵ ======


گراف زیر چند مسیر از $A$ به $B$ دارد؟ توجه کنید یک مسیر نمی‌تواند رأس یا یال تکراری داشته باشد.
{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۷:25-1.png?200 |}}
  - ۲۷۴
  - ۸۱
  - ۴۴
  - ۶۸
  - ۱۴۹

<راهنمایی>
به ازای هر راس تعداد مسیر‌هایی که به آن ختم می‌شود را بیابید.
</راهنمایی>

<راهنمایی>
رئوس گراف‌ را از چپ به راست و یکی یکی اضافه کنید و راهنمایی پیشین را اعمال کنید.
</راهنمایی>

<پاسخ>
 گزینه‌ی ۵ درست است.


رئوس را به شکل زیر شماره‌گذاری می‌کنیم:
{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۷:25-2.png?200 |}}
$g_n$
را تعداد مسیرهای از رأس
$n$
به $B$ تعریف می‌کنیم، طوری که از گام به صورت
$\leftarrow$
استفاده نشود. پاسخ در انتها برابر $g_9$
خواهد بود. با کمی بررسی متوجّه می‌شویم:
$$g_n = g_{n-1} + g_{n-2} + g_{n-3}$$
حال از آن‌جایی که
$g_0=1$،
$g_1=1$
و
$g_2=2$
داریم:
$$g_3 = 4 \Rightarrow g_4 = 7 \Rightarrow g_5 = 13 \Rightarrow g_6 = 24 \Rightarrow g_7 = 44 \Rightarrow g_8=81 \Rightarrow g_9 = 149$$
پس پاسخ برابر ۱۴۹ است.

</پاسخ>

  * [[سوال ۲۴|سوال قبل]]
  * [[سوال ۲۶|سوال بعد]]