المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲

در شکل مقابل اگر از هر نقطه بتوان به نقطه‌ی بالایی٬ راستی و بالا راستی رفت٬ چند مسیر به طول ۸ واحد از $A$ به $B$ وجود دارد؟

یکی از این مسیرها در شکل نشان داده شده است.

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

پاسخ

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

حرکت به سمت راست را با $r$، حرکت به سمت بالا با $u$و حرکت به سمت بالا راستی را با $o$ نمایش می‌دهیم. برای آن‌که مسیر طی شده از $A$ به $B$ به طول ۸ باشد٬ لازم است دو واحد از حرکات٬ بالاراستی٬ سه واحد از آن حرکات٬ به سمت راست و بالاخره سه واحد باقی‌مانده از ۸ حرکت به سمت بالا باشد. هر مسیری متناظر به خود دنباله‌ای متشکل از دو تا $o$ ٬ سه تا $r$ و سه تا $u$ دارد و برعکس. به عنوان مثال دنباله متناظر به مسیر مشخص شده در شکل به صورت orrouuru می‌باشد. تعداد دنباله‌های یاد شده(شامل دو حرف $o$، سه حرف $r$ و سه حرف $u$) برابر $\frac{8!}{2!\times3!\times3!}$ یعنی ۵۶۰ می‌باشد٬ بنابراین تعداد مسیرهای یادشده نیز برابر همین می‌باشد.


ابزار صفحه