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