سوال ۴

کشور یک‌طرفه‌های مسئله‌ی قبل (که شرط وجود جاده از شهر $i$ به شهر $j$٬ عبارت است از $i\lt j$) را در نظر بگیرید. حال تعداد روش‌های ساخت تعدادی جاده‌ی یک طرفه در این کشور را حساب کنید٬‌ به طوری که دو شرط زیر را داشته باشند:

  1. $۲^۹$
  2. $۴^۲$
  3. ۲۲
  4. ۱۸
  5. ۴

پاسخ

4) گزینه‌ی (3) درست است.

با توجه به شرط 1،از هر شهر دقیقا یک جاده‌ی یک طرفه خارج می شود. پس مجموع جاده‌های ورودی و خروجی شهر 1 دقیقا 1 است. مجموع جاده‌های ورودی و خروجی شهر 2 حداکثر 2، شهر 3 حداکثر 3 و شهر 4 حداکثر 4 است.

پس تنها در صورتی مجموع تعداد جاده‌های ورودی و خروجی شهر 4 بیش‌تر از 3 می‌شود که از شهرهای 1 و 2 و 3 جاده‌هایی به سمت 4 وجود داشته‌ باشد و از 4 یک جاده به 5 و تنها در حالتی مجموع جاده‌های ورودی و خروجی شهر 5 بیش‌تر از 3 می‌شود که هر 4 شهر با یک جاده‌ی یک طرفه مستقیما به آن متصل باشند.

پس این 2 حالت را از 24 حالت جواب مسئله‌ی قبل کم می‌کنیم و جواب 22 می‌شود.