سوال ۴
یک خرابه به شکل مقابل شش جایگاه دارد.
یک دزد در یکی از این جایگاه‌ها است. تیم امنیتی سلطان شامل تعدادی پلیس ماهر است. پلیس‌ها نمی‌دانند دزد کجا است و می‌خواهند او را دست‌گیر کنند. در ابتدای هر مرحله هر پلیس در یکی از جایگاه‌ها قرار می‌گیرد. اگر دزد در یکی از جایگاه‌هایی بود که پلیسی در آن قرار دارد، دست‌گیر می‌شود. در غیر این صورت پلیس‌ها از جایگاه‌ها خارج می‌شوند و دزد یکی از حرکات زیر را انجام می‌دهد:
- به جایگاه سمت راست خود می‌رود.
- به جایگاه سمت چپ خود می‌رود.
- به جایگاه روبه‌روی خود (با سه واحد فاصله) می‌رود.
سپس مجددا پلیس‌ها در جایگاه‌ها (نه لزوما جایگاه‌های مرحله‌ی قبل) قرار می‌گیرند و این مراحل تا یافتن دزد ادامه می‌یابد. با توجه به این نوع حرکات، تیم سلطان باید حداقل چند پلیس داشته باشد تا بتواند به طور تضمینی در تعداد محدودی مرحله دزد را دست‌گیر کند؟
- ۱
- ۲
- ۳
- ۴
- ۵
راهنمایی
اگر پلیس ها کمتر تعداد خانه های متفاوتی باشند که دزد در هر مرحله می تواند برود آنگاه ممکن است دزد در هر مرحله به خانه ای برود که پلیسی در آنجا نخواهد بود.
راهنمایی
خانه ها را یکی در میان سیاه سفید کنید دزد هر مرحله رنگ خانه اش عوض می شود.
پاسخ
گزینه‌ی ۳ درست است.
از آن‌جایی که دزد در هر مرحله به سه جای مختلف می‌تواند برود، پس اگر تعداد پلیس‌ها کمتر از سه تا باشد، ممکن است دزد در هر مرحله به جایی برود که پلیسی آن را پوشش نخواهد داد. پس پاسخ از ۳ کمتر نیست.
حال در جایگاه‌ها یک در میان پلیس بگذارید. فرض کنید دزد در مرحله‌ی اول دست‌گیر نشود، یعنی در یکی از سه خانه‌ی دیگر است. در مرحله‌ی دوم دوباره پلیس‌ها را همان‌جای قبل بگذارید. در هر صورت دزد به یکی از جایگاه‌های پلیس‌دار آمده است و دست‌گیر می‌شود. پس پاسخ برابر ۳ است.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
