سوال ۸
در شکل زیر هر کدام از نقطه‌ها، نشان‌دهنده‌ی یک شهر هستند. می‌خواهیم تعدادی جاده‌ی یک‌طرفه بین این شهرها احداث کنیم. جاده‌ها دو نوع هستند:
- جاده‌هایی که از یک شهر به اولین شهر سمت راستی آن کشیده می‌شوند.
- جاده‌هایی که از یک شهر به اولین شهر بالایی آن احداث می‌شوند.
به چند طریق می‌توانیم تعدادی جاده احداث کنیم، طوری که از شهر مبدأ به هر شهر دیگر دقیقاً یک مسیر وجود داشته باشد؟
- 42
- 512
- 32768
- 70
- 729
پاسخ
گزینه‌ی ۲ درست است.
جاده‌های ضلع سمت چپ و پایین باید تأسیس شوند. برای ۱۶ شهر دیگر تعداد راههای جاده‌زدن به آن‌ها (نه از آن‌ها) را می‌شماریم. برای هر کدام دقیقاً یک جاده‌ی ورودی باید وجود داشته باشد. اگر صفر جاده وجود داشته باشد، از شهر مبدأ نمی‌توان به آن شهر رسید و اگر هر دو جاده وجود داشته باشد، از دو راه می‌توان از شهر مبدأ به آن شهر رسید. بنابر این تعداد راههای تأسیس جاده برابر است با $2^16$.