سوال ۱

مریم می‌خواهد از بالاترین رأسِ گراف جهت‌دار زیر به پایین‌ترین رأس آن برود. او تنها می‌تواند در جهتِ مشخص‌شده روی یال‌ها حرکت کند و نمی‌تواند از هیچ رأسی بیش از یک بار عبور نماید. مریم به چند روش می‌تواند این مسیر را بپیماید؟

  1. $72$
  2. $48$
  3. $14$
  4. $96$
  5. $60$

پاسخ

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

اگر دو یال ابتدای مسیر و سه‌یال انتهای مسیر را انتخاب کنیم، باقی مسیر به شکل یکتا مشخص می‌شود. یال اول مسیر سه حالت دارد و بعد از انتخاب یال اول، یال دوم نیز دو حالت دارد. بنابراین:

$$ 3 \times 2 = 6 $$

حالت برای دو یال اول مسیر وجود دارد.

یال آخر مسیر دو حالت دارد و مشابه انتخاب‌های قبل، پس از انتخاب یال آخر، یال یکی مانده به آخر نیز دو حالت دارد، و به طور مشابه‌یال دو تا مانده به آخر نیز پس از انتخاب دو یال آخر دو حالت دارد. بنابراین:

$$ 2 \times 2 \times 2 = 8 $$

حالت برای سه‌یال آخر مسیر داریم.

بنابراین در مجموع:

$$ 3 \times 2 \times 2 \times 2 \times 2 = 48 $$

حالت برای این کار موجود است.

سوال بعد ◂