Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳۸

یک کشور با ۹ شهر داریم. همان‌طور که در شکل می‌بینید، تعدادی جاده‌ی یک‌طرفه بعضی از شهرها را به هم وصل کرده است. یک شهر، مثلِ a، را «خطرناک» می‌گوییم هرگاه شهر دیگری مثلِ b وجود داشته باشد، به صورتی که بتوان از a به b رفت، اما نتوان از b به a بازگشت. دولت قصد دارد ۲ جاده‌ی یک‌طرفه‌ی جدید احداث کند، به‌نحوی‌ که در نهایت دقیقاً ۳ شهرِ غیر خطرناک در آن کشور باقی بماند.

دولت به چند طریقِ مختلف می‌تواند این جاده‌ها را احداث کند؟

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

پاسخ

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

شکل داده شده از سه مولفه a،b و c تشکیل شده است. برای ساختن شبکه مطلوب باید به یکی از دو شکل abc و یا abc برسیم که تعداد کل حالات رسیدن به هر یک از آن‌ها به ترتیب به شکل زیر به‌دست می‌آید:

1)abc

  • انتخاب یک مولفه از سه مولفه برای آن‌که نقش a را بازی کند(این کار به ۳ طریق ممکن است).
  • انتخاب یک راس از رئوس آن برای آن‌که از آن راس فلشی خارج شود(این کار نیز به ۳ طریق ممکن است).
  • انتخاب یک مولفه از دو مولفه باقی‌مانده برای آن‌که نقش b را بازی کند(این کار به ۲ طریق ممکن است).
  • انتخاب یک راس از رئوس b برای آن‌که فلشی به آن وارد شود(به ۳ طریق).
  • انتخاب یک راس از رئوس b برای آن‌که فلشی از آن خارج شود(به ۳ طریق).
  • انتخاب یک راس از رئوس c برای آن‌که فلش خارج شده از b به آن وارد شود(به ۳ طریق).

طبق اصل ضرب تعداد کل طرق در این حالت برابر 3×3×2×3×3×3 یعنی ۴۸۶ می‌شود.

2)abc

  • انتخاب یک مولفه از مولفه برای آن‌که نقش b را بازی کند(به ۳ طریق).[البته مشخص است که دو مولفه a و c هم‌نقشند.]
  • انتخاب یک راس از رئوس a و یک راس از رئوس c برای آن‌که فلش‌هایی از آن‌ها خارج شود(3×3 طریق).
  • انتخاب یک راس از رئوس b برای وارد شدن فلش خارج شده از a و یک راس(نه لزوما متمایز از قبلی) از رئوس b برای وارد شدن فلش خارج شده از c(3×3 طریق).

در این حالت نیز مجموع کل طرق برابر 3×32×32 یعنی ۲۴۳ می‌شود.

باتوجه به حالت‌بندی فوق جواب مورد نظر 486+243 یعنی ۷۲۹ به‌دست می‌آید.


ابزار صفحه