В новой квартире после переезда остались стоять 5 пустых коробок, которые и полюбились коту: он начал в них спать. Коробки пронумерованы цифрами 1, 2, 3, 4, 5 и стоят в один ряд именно в таком порядке.
Проснувшись, кот выпрыгивает из коробки, а на следующую ночь отправляется спать в стоящую по соседству (слева либо справа) к той коробке, в которой он находился перед этим. Вам разрешается утром открыть лишь одну коробку и проверить, не в ней ли спит кот.
Нам неизвестно, в какой именно коробке кот ночевал в первый раз. Есть ли стратегия, позволяющая однажды гарантированно отыскать кота? Логику и жизненность в этой задаче искать не нужно, давайте просто начнем рассуждать.
Решение
Раз кот постоянно переходит спать в стоящую по соседству коробку, значит, он ночует по очереди то в четном «номере», то в нечетном. Воспользуемся этим для решения.
Вариант 1: Первую ночь кот провел в коробке с четным числом
То есть кот начал со второй или четвертой коробки. Предположим, первой мы откроем коробку №2: кот в ней – мы победили, если нет – то он спит в коробке №4. А раз так, значит, завтра он отправится ночевать в коробку №3 или №5.
На следующий день смотрим в коробку №3: кот в ней – мы победили, если нет – то он находится в коробке №5. Это говорит о том, что ближайшей ночью он будет спать в четвертой коробке, так как у пятой другой соседней нет.
Третьим утром мы открываем коробку №4 и обнаруживаем в ней кота. Задача выполнена!
Вариант 2: Первую ночь кот провел в коробке с нечетным числом
Если предыдущий алгоритм не сработал, и кота в коробке №4 не оказалось, значит, он начал ночевать в нечетной коробке. Первое утро - нечетная коробка, второе утро – четная, третье – опять нечетная.
Выходит, что на четвертую ночь кот будет спать снова в коробке с четным номером: или 2, или 4. Именно с этого мы начали поиски в предыдущем варианте, значит, нам нужно просто повторить описанную выше стратегию: по очереди открыть коробки №2, №3 и №4.
Старайтесь чаще думать над решением подобных задач, потому что разработчику очень важно регулярно качать свою «алгоритмическую мышцу»!