Перевод для 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.
Понравилась статья? Оцените ее:
Система Orphus: Если вы заметили ошибку в тексте, выделите ее и нажмите Ctrl + Enter
© Mixstuff 2012. Права на опубликованный перевод принадлежат владельцам вебсайта mixstuff.ru
Все графические изображения, использованные при оформлении статьи принадлежат их владельцам. Знак охраны авторского права распространяется только на текст статьи.
Использование материалов сайта без активной индексируемой ссылки на источник запрещено.
[ comments ]