====== سوال ۱ ======

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

{{:سوالات_المپیاد:مرحله‌ی_دوم:دوره‌ی_۳۴/img_1.png|}}




  - $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
$$
  
حالت برای این کار موجود است.

.
</پاسخ>
  * [[سوال ۲|سوال بعد]]