المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۹:سوال ۱۷

سوال ۱۷

در شکل روبه‌رو هر نقطه را یک شهر و هر پاره‌خط را یک جاده بین دو شهر فرض کنید. بعضی از این جاده‌ها به صورت یک طرفه جهت‌دار شده‌اند. می‌خواهیم بقیه‌ي این جاده‌ها را طوری به صورت یک طرفه جهت‌دار کنیم که از هیچ شهری نتوان با حرکت روی جاده‌ها٬ به خودش رسید.

به چند طریق این کار ممکن است؟

  1. ۴
  2. ۶
  3. ۸
  4. ۹
  5. ۱۶

پاسخ

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

هر یک از دو زوج یال‌ها موجود در سمت چپ و راست شکل را به طور مستقل از یکدیگر به سه طریق می‌توان جهت‌دار کرد. بنابراین طبق اصل ضرب جواب مورد نظر برابر $3\times3$ یعنی ۹ می‌باشد.


ابزار صفحه