سوال ۱
مریم میخواهد از بالاترین رأسِ گراف جهتدار زیر به پایینترین رأس آن برود. او تنها میتواند در جهتِ مشخصشده روی یالها حرکت کند و نمیتواند از هیچ رأسی بیش از یک بار عبور نماید. مریم به چند روش میتواند این مسیر را بپیماید؟
- $72$
- $48$
- $14$
- $96$
- $60$
پاسخ
گزینه (۲) درست است.
اگر دو یال ابتدای مسیر و سهیال انتهای مسیر را انتخاب کنیم، باقی مسیر به شکل یکتا مشخص میشود. یال اول مسیر سه حالت دارد و بعد از انتخاب یال اول، یال دوم نیز دو حالت دارد. بنابراین:
$$ 3 \times 2 = 6 $$
حالت برای دو یال اول مسیر وجود دارد.
یال آخر مسیر دو حالت دارد و مشابه انتخابهای قبل، پس از انتخاب یال آخر، یال یکی مانده به آخر نیز دو حالت دارد، و به طور مشابهیال دو تا مانده به آخر نیز پس از انتخاب دو یال آخر دو حالت دارد. بنابراین:
$$ 2 \times 2 \times 2 = 8 $$
حالت برای سهیال آخر مسیر داریم.
بنابراین در مجموع:
$$ 3 \times 2 \times 2 \times 2 \times 2 = 48 $$
حالت برای این کار موجود است.
| سوال بعد ◂ |
