Кот Леопольд очень голоден. Он хочет поймать и съесть мышь любой ценой, но желательно побыстрее.
Мышь спряталась за стеной, она находится в системе из пяти норок, расположенных рядом друг с другом, на одной прямой линии. Каждая пара соседних норок (1-я и 2-я; 2-я и 3-я; 3-я и 4-я; 4-я и 5-я) соединены между собой ходом. Очевидно, ходы спрятаны где-то в толще стены.
Кот Леопольд не знает, где именно находится мышь, так как он её не видит. Но он знает, что перед каждой его попыткой она непременно находится где-то в одной из этих пяти норок. При каждой своей попытке кот может засунуть лапу в одну из норок (но только в какую-то одну) и проверить эту норку на наличие мыши. Если попытка оказалась удачной, то мышь поймана. Если же попытка оказалась неудачной и мыши в исследуемой норке не оказалось, то мышь до начала следующей попытки кота обязательно перебегает в соседнюю норку (таково условие задачи). Например, из норки № 3 в случае неудачи кота мышка может перебежать или в норку № 2, или в норку № 4. Из норки № 1 — только в № 2; из № 5 — только в № 4.
Количество попыток у Леопольда не ограничено, но он желает поймать мышь по возможности за наименьшее количество попыток.
Вопрос: может ли при таких условиях Леопольд вообще поймать мышку и если да, то сколько попыток ему понадобится и каков будет алгоритм поимки мыши?
Добавить комментарий