المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۵

دو نفر روی مبدأ محور ‎$x$‎ ایستاده‌اند. در هر مرحله هر کدام به‌طور مستقل یک واحد به چپ یا راست می‌روند. به‌چند طریق ممکن است بعد از ‎۵‎ مرحله هر دو نفر در یک مکان باشند؟

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

پاسخ

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

تعداد طرقی که آن دو در نقطه‌ی ۵ با هم ملاقات کنند برابر $1^2$ می‌باشد. تعداد طرقی که آن دو در نقطه‌ی ۳ باهم ملاقات کنند برابر $\binom{5}{1}^2$؛ یعنی ۲۵ می‌باشد. در حقیقت هر یک از آن دو نفر به $\binom{5}{1}$ طریق می‌توانند یکی از ۵ حرکت خود را به عنوان حرکت برگشتی انتخاب کنند.

تعداد طرقی که آن دو در نقطه‌ی۱ باهم ملاقات کنند برابر $\binom{5}{2}^2$؛ یعنی ۱۰۰ می‌باشد. در حقیقت هر یک از آن دونفر به $\binom{5}{2}$ طریق می‌توانند دو تا از ۵ حرکت خود را به عنوان حرکت برگشتی انتخاب کنند.

تعداد طرق ملاقات آن دو در نقاط ۵-،۳- و ۱- نیز به همان صورت به دست می‌آید. پس جواب مطلوب برابر $2(1+25+100)$ یعنی ۲۵۲ می‌باشد.

یادآوری می‌شود که امکان ملاقات آن دو در نقاط زوج غیر ممکن است.


ابزار صفحه