سوال ۴

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

از هر کدام از شهرهای ۱ تا ٬۴ دقیقاً یک مسیر (شامل یک یا چند جاده‌ی یک‌طرفه) به شهر ۵ وجود داشته باشد (همان شرط مسئله‌‌ی قبل).
به ازای هر شهر٬‌ مجموع تعداد جاده‌هایی که از آن شهر شروع می‌شوند٬ به علاوه‌‌ی تعداد جاده‌هایی که به آن شهر ختم می‌شوند٬ از سه تا بیشتر نباشد.

$۲^۹$
$۴^۲$
۲۲
۱۸
۴

پاسخ

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 می‌شود.