Как и обещали, публикуем ответ на вчерашнюю головоломку

Перевод для mixstuff – Дмитрий Уточкин

Вчера мы опубликовали головоломку, которая заключается в следующем:

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

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

Итак, сколько дней вам понадобится, чтобы найти кошку?

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

Для многих головоломок такого типа ключом к разгадке является визуализация. Ниже представлена таблица, показывающая, что происходит, когда есть четыре двери. Каждый столбец представляет собой дверь. Если кошка находится в колонке, это означает, что кошка может быть за этой дверью. Красным крестиком я обозначаю дверь, которую открываю. Сейчас мы рассмотрим это более подробно.

В День 1 кошка может прятаться за любой из четырёх дверей, поэтому в каждой колонке таблицы есть изображение кошки. Я открываю дверь 2. Если кошка там – я победил.

В День 2 кошка может быть только за дверями 2,3 и 4. Всё потому, что мы устранили вероятность того, что кошка была за дверью 2 в первый день. И если кошка стояла за дверями 1, 3 или 4 в день 1, она может быть теперь за дверью2, 3 и 4. Я открываю дверь 3. Если кошка там – я победил.

В День 3 кошка может быть только за дверью 1 и 3. Я открываю дверь 3, а это означает, что в День 4 есть только одно возможное положение для кошки – дверь 2. Я открывал двери в следующем порядке: 2,3,3,2. Эта стратегия позволяет поймать кошку не более, чем за четыре дня.

Если в условии головоломки пять дверей, таблица выглядит несколько иначе. Но, если получилось решить задачу с четырьмя дверьми, несложно будет немного расширить нашу стратегию: открываем двери 2,3,4,4,3,2 по порядку.

Как видите, решение немного усложняется: вы начинаете со второй двери в День 1, двигаетесь каждый день дальше до предпоследней двери, а потом возвращаетесь. Итак, для того чтобы решить головоломку с семью дверями, вам нужно открывать двери в следующей последовательности: 2,3,4,5,6,6,5,4,3,2.Значит, на решение задачи уйдёт десять дней.

Вообще, можно продолжать добавлять двери до бесконечности – вы всегда найдёте кошку. Для расчёта необходимого количества дней подойдёт следующая формула: (количество дверей – 2)x 2.