Processing math: 80%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۸

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

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

پاسخ

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

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

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


ابزار صفحه