المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۴

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

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

پاسخ

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

برای رسیدن از $A$‎ به $B$‎ یکی از دو حالت زیر اتفاق می‌افتد:

  1. چهار حرکت راست($R$)، یک حرکت پایین($L$) و سه حرکت بالا ($U$). تعداد دنباله‌های متشکل از چهار $R$، یک $L$ و سه $U$ که هر دنباله متناظر به یک مسیر مطلوب می‌باشد برابر $\binom{8}{1} \binom{7}{3} \binom{4}{4}$ یعنی ۲۸۰ می‌باشد.
  2. پنج حرکت راست($R$)، یک حرکت چپ ($L$) و دو حرکت بالا ($U$). تعداد دنباله‌های متشکل از پنج $R$، یک $L$ و دو $U$ که هر دنباله متناظر به یک مسیر مطلوب می‌باشد برابر $\binom{8}{1} \binom{7}{5} \binom{2}{2}$ یعنی ۱۶۸ می‌باشد.

معلوم است که تعداد کل مسیرهای مطلوب برابر $280+168$ یعنی ۴۴۸ می‌باشد.


ابزار صفحه