Жил-был кот у тёти Вали,
Котофеем, помню, звали.
Занял целую террасу
И ни в чём не знал отказу —
Ни в сосиске, ни в сметане,
А меж тем под ним в чулане
Жил мышонок-невидимка
В пятикомнатной квартирке.
Все пять комнаток, конечно,
Были там попарно смежны,
И из всех своих каморок
Он прогрыз пятёрку норок.
Слух у Котофея тонок:
Слыша, как скребёт мышонок,
Он стряхнул с себя дремоту
И помчался на охоту.
Два прыжка — и он в чулане;
В нос мышиным духом тянет,
А в стене подряд пять норок,
Не поймёшь, откуда шорох.
Где мышонок, кот не знает —
В середине или с краю,
Но, просунув в норку лапу,
Угадает — может сцапать.
Если он не угадает,
Мышь всегда перебегает
Из каморки, где сидела,
Рядом вправо или влево.
Расскажи, в каком порядке
Надо в норки лазить лапкой,
Если наш котяра хочет
Всё закончить покороче,
Ну а мышь дрожит за шкуру
И притом совсем не дура?
Сколько сделает ходов
Самый умный из котов?
Ответ: 6 ходов: 2, 3, 4, 2, 3, 4.
Решение.
Занумеруем норки слева направо.
Заметим, что после каждого хода кота мышка перебегает в норку другой чётности.
Для Котофея лучше вариант, если вначале мышь сидела в норке 2 или 4 (с чётным номером). Поэтому он лезет в норку 2 (для определённости; мог бы и в норку 4). Раз мышки там нет (она же не дура! и тоже знает, как кот будет себя вести), то, по мнению кота, она сидела в норке 4 и перешла в 3 или 5.
2-й ход кота: 3; предотвращается перебегание в норки с маленькими номерами. Кот делает вывод, что, значит, мышка в норке 5, а оттуда обязательно должна попасть в норку 4.
3-й ход кота: 4. Раз мышки там нет, значит, начальное предположение неверно, и вначале она была в нечётной норке, перед 3-м ходом кота тоже была в нечётной норке, а после него перебежит в чётную норку.
Ходы 4-6 кота: то же, что ходы 1-3, но теперь всё делается не в предположении, а в уверенности, что перед 4-м ходом кота мышка была в чётной норке.