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