====== سوال ۸ ======

در شکل زیر هر کدام از نقطه‌ها، نشان‌دهنده‌ی یک شهر هستند. می‌خواهیم تعدادی جاده‌ی
__یک‌طرفه__
 بین این شهرها احداث کنیم. جاده‌ها دو نوع هستند:


  * جاده‌هایی که از یک شهر به اولین شهر سمت راستی آن کشیده می‌شوند.
  * جاده‌هایی که از یک شهر به اولین شهر بالایی آن احداث می‌شوند.

به چند طریق می‌توانیم تعدادی جاده احداث کنیم، طوری که از شهر مبدأ به هر شهر دیگر دقیقاً یک مسیر وجود داشته باشد؟
{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۹:untitled113.png |}}

  - 42
  - 512
  - 32768
  - 70
  - 729


<پاسخ>
 گزینه‌ی ۲ درست است.


جاده‌های ضلع سمت چپ و پایین باید تأسیس شوند. برای ۱۶ شهر دیگر تعداد راه‌های جاده‌زدن به آن‌ها (نه از آن‌ها) را می‌شماریم. برای هر کدام دقیقاً یک جاده‌ی ورودی باید وجود داشته باشد. اگر صفر جاده وجود داشته باشد، از شهر مبدأ نمی‌توان به آن شهر رسید و اگر هر دو جاده وجود داشته باشد، از دو راه می‌توان از شهر مبدأ به آن شهر رسید. بنابر این تعداد ر‌اه‌های تأسیس جاده برابر است با $2^16$.



</پاسخ>

  * [[سوال ۷|سوال قبل]]
  * [[سوال ۹|سوال بعد]]