المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۸

در شکل روبه‌رو می‌خواهیم با پیمودن کوتاه‌ترین مسیر روی خطوط شبکه، از نقطه‌ی ‎$A$‎ به نقطه‌ی ‎$B$‎ برویم. این کار به‌چند طریق امکان پذیر است؟

  1. ۱۰
  2. ۲۸
  3. ۳۲
  4. ۴۴
  5. ۵۶‎

پاسخ

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

بعضی از خطوط شبکه اضافه بوده و هرگز از آن‌ها نمی‌توان عبور کرد. با حذف آن خطوط٬ شبکه‌ی جدید به صورت زیر در می‌آیند:

تعداد مسیرهای مطلوب در شبکه‌ی فوق با تعداد مسیرهای از $A$ به $B$ در شبکه‌ی زیر تفاوتی ندارد که این تعداد برابر $\binom{3+5}{3}$؛ یعنی ۵۶ می‌باشد.


ابزار صفحه