Question

Как решается задача о коте Леопольде, мыши и пяти норках?

Кот Леопольд очень голоден. Он хочет поймать и съесть мышь любой ценой, но желательно побыстрее.

Мышь спряталась за стеной, она находится в системе из пяти норок, расположенных рядом друг с другом, на одной прямой линии. Каждая пара соседних норок (1-я и 2-я; 2-я и 3-я; 3-я и 4-я; 4-я и 5-я) соединены между собой ходом. Очевидно, ходы спрятаны где-то в толще стены.

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

Количество попыток у Леопольда не ограничено, но он желает поймать мышь по возможности за наименьшее количество попыток.

Вопрос: может ли при таких условиях Леопольд вообще поймать мышку и если да, то сколько попыток ему понадобится и каков будет алгоритм поимки мыши?

Answer 1

Очевидно, необходимо вначале принять решение в какой норе может быть мышь, а затем вариант очередности проверки. В виду того, что мышь после каждой попытки кота перебегает в соседнюю нору, она последовательно чередует нечетные норы с четными. Предположим, она находится в нечетной норе.

• Проверяем 3 нору, если ее там нет, значит в 1 или 5 и перебежит во 2 или 4.
• Следующая попытка нора 2, опять пусто, значит в 4 норе, и дальше скроется в 3 или 5.
• Теперь коту необходимо опробовать 3 нору, что бы исключить возможность мыши перебраться на другую сторону норок, а мыши скрыться 5 норе.
• Следующий ход - обследование 4 норы, в которой должна оказаться мышь при правильном первоначальном нашем предположении. В противном случае, мышь укрылась в начале игры в четной норе, а в данный момент находится в нечетной.
• Проверяем повторно 4 нору, так она должна уже быть в одной из четных норах.
• Если ее нет, значит, она была в норе под номером 2. Тогда коту остается засунуть лапу в 3 нору и если попытка окажется неудачной, мыши согласно правилам придется из первой норы перебраться в нору под номером 2, где и постигнет ее печальная участь.