المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۵

همان سوال قبل را در نظر بگیرید، با این تفاوت که دزد در هر مرحله یکی از حرکات زیر را انجام می‌دهد:

  • یک واحد به سمت راست خود حرکت می‌کند.
  • دو واحد به سمت چپ خود حرکت می‌کند.

در این صورت حداقل چند پلیس لازم است؟

  1. ۱
  2. ۲
  3. ۳
  4. ۴
  5. ۵

پاسخ

گزینه‌ی ۲ درست است.

مانند استدلال قسمت قبل ثابت می‌شود حداقل دو پلیس لازم است. حال روشی ارائه می‌دهیم که سلطان بتواند با دو پلیس، دزد را دست‌گیر کند. جایگاه‌ها را به شکل مقابل با شماره‌های $1, 2, ..., 6$ شماره‌گذاری کنید:

  • اگر دزد در جایگاه ۱ یا ۴ باشد، به جایگاه ۲ یا ۵ می‌رود.
  • اگر دزد در جایگاه ۲ یا ۵ باشد، به جایگاه ۳ یا ۶ می‌رود.
  • اگر دزد در جایگاه ۳ یا ۶ باشد، به جایگاه ۱ یا ۴ می‌رود.

حال همواره در هر مرحله پلیس‌ها را در جایگاه‌های ۱ و ۴ بگذارید. حداکثر در مرحله‌ی سوم دزد به این خانه‌ها خواهد آمد و دست‌گیر می‌شود. پس پاسخ برابر ۲ است.


ابزار صفحه