سوال ۱۲
در نقشه‌ی روبه‌رو٬ نقاط پررنگ نشان‌دهنده‌ي شهر و کمان‌ها و پاره‌خط‌های مستقیم بین آنها جاده هستند. برای ما استفاده از جاده‌های مستقیم و کمانی تفاوتی ندارد. به چند طریق می‌توان با کم‌ترین تعداد جاده از شهر $A$ به شهر $B$ رفت؟
(دقت کنید که صرفاً تعداد جاده‌ها مهم است و بین بعضی از شهرها دو یا سه جاده قرار دارد.)
- $۲^۷ \times ۳^۴$
- $۲^۸ \times ۳^۳$
- $۲^{۱۱} \times ۳^۴$
- $۳^{۱۱} \times ۲^۷$
- $۶^۴ \times ۲^۵$
پاسخ
گزینه‌ی (1) درست است.
دایره‌ها به گونه‌ای تقسیم شده‌اند که یکی از کمان‌های کامل آنها مسیری با 4 پاره خط دارد و کمان دیگر 3 تا.از هر دایره مسیر 3خطی را انتخاب می‌کنیم.پس در کل 11 جاده را می‌پیماییم. از 7 تا از نقاط تقاطع دایره‌ها 2 جاده برای انتخاب وجود دارد و از 4تای آنها 3 جاده. پس طبق اصل ضرب تعداد روش‌های رسیدن از$A$ به $B$ با کم‌ترین تعداد جاده $3^4 \times 2^7$ می‌شود.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
