Loading [MathJax]/jax/output/HTML-CSS/jax.js

سوال ۲۹

در شکل مقابل، اگر بتوان از روی خطوط فقط در جهت چپ به راست حرکت کرد، تعداد مسیرهای مختلف بین A و B برابر است با:

  1. ۵۴
  2. ۸۱
  3. ۱۶۲
  4. ۲۴۳
  5. ۴۸۶

پاسخ

گزینه (۳) درست است.

در سمت چپ هر گره‌ای مانندm، حداکثر دو گروه مانند n و k وجود دارد. تعداد راه‌های رسیدن به گره m با مجموع تعداد راه‌های رسیدن به دو گره n و k برابر است٬ بنابراین تعداد راه‌های رسیدن به هر گره مطابق شکل زیر می‌باشد: