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