المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۴

مهره‌ای بر روی نقطه‌ی مبدأ صفحه‌ی مختصات قرار دارد. در هر حرکت می‌توانیم مهره را از نقطه‌ی ($x, y$) به نقطه‌ی ( $x+1, y+1$ )یا به نقطه‌ی ( $ x٫ y-1$) ببریم. به چند طریق می‌توانیم این مهره‌ها را به نقطه‌ی (۰ ۴٫) برسانیم ؟

  1. ۳۵
  2. ۱۶
  3. ۲۵۶
  4. ۷۰
  5. به نامتناهی روش

پاسخ

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

حرکت از نوع دوم مهره را به سمت راست منتقل نمی‌کند. بنابراین باید دقیقا ۴بار از حرکت نوع اول استفاده کرد. چون حرکت نوع اول یک واحد مهره را به سمت بالا منتقل می‌کند باید برای خنثی کردن آن جهت یک بار نیز از حرکت دوم استفاده شود٬ در نتیجه در مجموع ۸ حرکت استفاده خواهد شد که چهار تا از آن‌ها از نوع اول و چهار تا از آن‌ها از نوع دوم می‌باشد. تعداد جایگشت‌های ۸شی که چهار تا از آن‌ها٬ شبیه هم و چهار تای دیگر نیز شبیه هم هستند برابر $\frac{8!}{4!4!}$ یا ۷۰ می‌باشد٬ به عنوان مثال مسیر متناظر به جایگشت ۲٬۲٬۱٬۲٬۱٬۱٬۱٬۲ مطابق شکل مقابل می‌باشد.


ابزار صفحه