Помогите найти кота!

В новой квартире после переезда остались стоять 5 пустых коробок, которые и полюбились коту: он начал в них спать. Коробки пронумерованы цифрами 1, 2, 3, 4, 5 и стоят в один ряд именно в таком порядке.

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

Нам неизвестно, в какой именно коробке кот ночевал в первый раз. Есть ли стратегия, позволяющая однажды гарантированно отыскать кота? Логику и жизненность в этой задаче искать не нужно, давайте просто начнем рассуждать.

Решение

Раз кот постоянно переходит спать в стоящую по соседству коробку, значит, он ночует по очереди то в четном «номере», то в нечетном. Воспользуемся этим для решения.

Вариант 1: Первую ночь кот провел в коробке с четным числом

То есть кот начал со второй или четвертой коробки. Предположим, первой мы откроем коробку №2: кот в ней – мы победили, если нет – то он спит в коробке №4. А раз так, значит, завтра он отправится ночевать в коробку №3 или №5. 

На следующий день смотрим в коробку №3: кот в ней – мы победили, если нет – то он находится в коробке №5. Это говорит о том, что ближайшей ночью он будет спать в четвертой коробке, так как у пятой другой соседней нет.

Третьим утром мы открываем коробку №4 и обнаруживаем в ней кота. Задача выполнена!

Вариант 2: Первую ночь кот провел в коробке с нечетным числом

Если предыдущий алгоритм не сработал, и кота в коробке №4 не оказалось, значит, он начал ночевать в нечетной коробке. Первое утро - нечетная коробка, второе утро – четная, третье – опять нечетная. 

Выходит, что на четвертую ночь кот будет спать снова в коробке с четным номером: или 2, или 4. Именно с этого мы начали поиски в предыдущем варианте, значит, нам нужно просто повторить описанную выше стратегию: по очереди открыть коробки №2, №3 и №4.

Старайтесь чаще думать над решением подобных задач, потому что разработчику очень важно регулярно качать свою «алгоритмическую мышцу»!