المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۹

سه توپ سیاه و سه توپ سفید داریم که به شکل زیر، در هفت جعبه جای گرفته‌اند:

فاصله‌ی دو جعبه تعداد جعبه‌های بین آن دو است. برای مثال فاصله‌ی دو جعبه‌ی مجاور صفر است. در هر حرکت می‌توان یک توپ که فاصله‌ی جعبه‌اش با یک جعبه‌ی خالی، حداکثر یک است را به خانه‌ی خالی انتقال داد. می‌خواهیم به حالتی برسیم که سه توپ سفید در سه جعبه‌ی سمت چپ و سه توپ سیاه در سه جعبه‌ی سمت راست باشند. حداقل چند حرکت برای این کار لازم است؟

  1. ۱۴
  2. ۱۶
  3. ۱۷
  4. ۱۳
  5. ۱۵

پاسخ

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

تعداد جابجایی‌ها برای هر توپ چهار خانه است. در نتیجه هر توپ حداقل باید دو حرکت انجام دهد تا به خانه‌ی هدفش برسد (12 حرکت). از طرف دیگر حرکت اول و آخر همواره شامل یک واحد حرکت هستند. در نتیجه هر کدام از آن مهره‌ها باید یک حرکت اضافه‌تر انجام دهند که در مجموع 14 حرکت می‌شود.

اگر 14 جواب مسئله باشد باید بتوان با همین روند (بجز دو حالت همواره حرکات 2 واحدی) به انتها رسید. کافیست از حرکت اول دنباله‌ی حرکت را پیگیری کنیم تا ببینیم پس از پنج حرکت بازی به حالتی می‌رسد که باید یک حرکت یک واحدی اضافی انجام شود و در نتیجه تعداد حرکات برای رسیدن به جواب 15 می‌شود.

از طرفی با ادامه دادن همین روند مثالی با 15 حرکت هم یافت می‌شود.


ابزار صفحه