المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی اول:دوره‌ی ۹:سوال ۴۰

سوال ۴۰

پنج شهر $D،C،B،A$ و $E$ را در نظر بگیرید. قراراست به هر کدام از شهرهای $B،A$ و $C$ دو جاده و به هر یک از شهرهای $D$ و $E$ یک جاده متصل باشد.

به چند طریق می‌توان این شهرها را با تعداد لازم جاده به هم وصل کرد به طوری که به هر شهر به تعداد فوق جاده متصل باشد و نیز از هر شهر بتوان با حرکت روی جاده‌ها به تمام شهرهای دیگر رفت؟

  1. ۴
  2. ۵
  3. ۶
  4. ۷
  5. ۸

پاسخ

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

شهر متصل به $D$ یکی از شهر‌های $B،A$ یا $C$ می‌باشد زیرا اگر $D$ به $E$ متصل باشد آن‌گاه شهر $D$ به غیر از $E$ به هیچ شهر دیگری مسیر نخواهد داشت. به همین صورت $E$ نیز به یکی از شهر‌های $B،A$ یا $C$ (به غیر از شهری که $D$ به آن متصل است) وصل خواهد بود. بنابراین تعداد جواب‌های ممکن برابر $3\times2$ یعنی ۶ خواهد بود.


ابزار صفحه