Processing math: 100%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۳۴:سوال ۱

سوال ۱

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

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

پاسخ

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

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

3×2=6

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

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

2×2×2=8

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

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

3×2×2×2×2=48

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

.


ابزار صفحه