سوال ۵
همان سوال قبل را در نظر بگیرید، با این تفاوت که دزد در هر مرحله یکی از حرکات زیر را انجام می‌دهد:
- یک واحد به سمت راست خود حرکت می‌کند.
- دو واحد به سمت چپ خود حرکت می‌کند.
در این صورت حداقل چند پلیس لازم است؟
- ۱
- ۲
- ۳
- ۴
- ۵
راهنمایی
دایره ها را شماره گذاری کنید از ۱ تا ۶ و ببینید دزد از هر خانه به چه دو خانه ای می رود.
راهنمایی
سه دسته دوتایی از خانه ها بر اساس اینکه دزد از آن هابه چه خانه ای می رود به وجود می آید که ترتیب رفتن دزد به این دسته ها در یک لوپ تکرار می افتد.
پاسخ
گزینه‌ی ۲ درست است.
مانند استدلال قسمت قبل ثابت می‌شود حداقل دو پلیس لازم است. حال روشی ارائه می‌دهیم که سلطان بتواند با دو پلیس، دزد را دست‌گیر کند. جایگاه‌ها را به شکل مقابل با شماره‌های $1, 2, ..., 6$ شماره‌گذاری کنید:
- اگر دزد در جایگاه ۱ یا ۴ باشد، به جایگاه ۲ یا ۵ می‌رود.
- اگر دزد در جایگاه ۲ یا ۵ باشد، به جایگاه ۳ یا ۶ می‌رود.
- اگر دزد در جایگاه ۳ یا ۶ باشد، به جایگاه ۱ یا ۴ می‌رود.
حال همواره در هر مرحله پلیس‌ها را در جایگاه‌های ۱ و ۴ بگذارید. حداکثر در مرحله‌ی سوم دزد به این خانه‌ها خواهد آمد و دست‌گیر می‌شود. پس پاسخ برابر ۲ است.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
