سوال ۲۵

گزینه‌ی ۵ درست است.

رئوس را به شکل زیر شماره‌گذاری می‌کنیم: $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$$ پس پاسخ برابر ۱۴۹ است.