سوال ۳
کشور یک‌طرفه‌ها٬ پنج شهر به شماره‌های ۱ تا ۵ دارد. تنها در صورتی می‌توان از شهر i به شهر j یک جاده‌ی یک‌طرفه کشید٬ که i<j باشد؛ در صورت ساخت چنین جاده‌ای٬ با استفاده از این جاده می‌توان از شهر i به شهر j رفت٬ ولی نه برعکس. به چند طریق می‌توان تعدادی جاده‌ی یک طرفه در این کشور ساخت به طوری که٬ از هر کدام از شهرهای ۱ تا ۴ دقیقاً یک مسیر (تشکیل شده از یک یا چند جاده‌ی یک‌طرفه‌ي پشت سر هم) به شهر ۵ وجود داشته باشد؟
- ۲۱۰
- ۴۴
- ۵۵
- ۲۴
- ۵
پاسخ
گزینه‌ی (4) درست است.
از شهر 4 به 5 تنها یک مسیر وجود دارد که همان جاده‌ی یک طرفه از 4 به 5 است.برای هر شهر 1≤i≤3 باید بین i و دقیقا یکی از شهرها با شماره‌ی بزرگ‌تر جاده رسم کرد. یعنی به 5−i طریق می توان جاده رسم کرد که دقیقا یک مسیر از i به 5 وجود داشته باشد. پس تعداد کل حالت‌ها 1×2×3×4=24 است.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
