یک کشور با ۹ شهر داریم. همانطور که در شکل میبینید، تعدادی جادهی یکطرفه بعضی از شهرها را به هم وصل کرده است. یک شهر، مثلِ a، را «خطرناک» میگوییم هرگاه شهر دیگری مثلِ b وجود داشته باشد، به صورتی که بتوان از a به b رفت، اما نتوان از b به a بازگشت. دولت قصد دارد ۲ جادهی یکطرفهی جدید احداث کند، بهنحوی که در نهایت دقیقاً ۳ شهرِ غیر خطرناک در آن کشور باقی بماند.
دولت به چند طریقِ مختلف میتواند این جادهها را احداث کند؟
پاسخ
گزینه (۵) درست است.
شکل داده شده از سه مولفه a،b و c تشکیل شده است. برای ساختن شبکه مطلوب باید به یکی از دو شکل a→b→c و یا a→b←c برسیم که تعداد کل حالات رسیدن به هر یک از آنها به ترتیب به شکل زیر بهدست میآید:
1)a→b→c
طبق اصل ضرب تعداد کل طرق در این حالت برابر 3×3×2×3×3×3 یعنی ۴۸۶ میشود.
2)a→b←c
در این حالت نیز مجموع کل طرق برابر 3×32×32 یعنی ۲۴۳ میشود.
باتوجه به حالتبندی فوق جواب مورد نظر 486+243 یعنی ۷۲۹ بهدست میآید.