المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۲:سوال ۳۰

سوال ۳۰

اگر در شکل روبه‌رو طول اضلاع همه‌ی شش ضلعی‌ها با هم یکسان باشد، تعداد کوتاه‌ترین مسیرهای ممکن بین ‎$A$ و ‎$B$‎ به نحوی که فقط از روی اضلاع شش ضلعی‌ها حرکت کنیم چقدر است؟

  1. ۱۶
  2. ۲۴
  3. ۷۰
  4. ۲۵۲
  5. ۲۵۶

پاسخ

گزینه (۳) درست است.

خانه‌هایی که هاشور خورده‌اند در مسیر مطلوب شرکت ندارند. شکل باقی‌مانده یک شبکه‌ی $4\times4$ می‌باشد که تعداد مسیرهای کوتاه موجود از گوشه‌ی چپ و پایین آن به گوشه‌ی راست و بالای آن برابر $\binom{8}{4}$؛ یعنی ۷۰ می‌باشد.


ابزار صفحه