سوال ۴
کشور یک‌طرفه‌های مسئلهی قبل (که شرط وجود جاده از شهر $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 می‌شود.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
