Представь, что ты глава самой обычной сибирской семьи. Каждый Новый год вы подаете к столу ароматного жареного медведя, однако в этот раз медведь попался хитрый.
Задача
Во дворе (позади стойла с единорогами) у вас размещены в ряд пять будок. Медведь ночует в одном из этих ящиков. Каждую ночь он тайком перебирается в соседний ящик — либо тот, что справа, либо тот, что слева.
Каждое утро вы можете открыть и проверить лишь одну из пяти будок. Так требует древний мистический ритуал. Иначе медведь будет невкусным.
Вопрос
Как до праздника обнаружить медведя, которого ровно за неделю до Нового года посадили неизвестно в какую из будок?
Чтобы проверить правильность решения, достаточно пролистать статью вниз.
У нас хватает таких веселых оптимистичных загадок. Тебе понравится головоломка про русскую рулетку.
Разгадка
Возня предстоит нешуточная. Нет смысла проверять каждый день один и тот же ящик. И точно так же нет смысла идти по порядку и каждый день проверять следующий по номеру ящик. К тому же напоминаем, что у нас семь дней на вычисление медведя.
Шаг 1. Для начала выстроим упрощенную математическую модель. Предположим, будто медведь на Новый год сидит в ящике с четным номером. Или 2, или 4. Мы проверим ящик 2, и найдем его там. А если не найдем, то он в ящике 4.
Теперь представим, будто это только первый день из предновогодней недели. В первый день вы проверили ящик 2, там было пусто, и это дает точный знак, что медведь — в ящике 4.
Логичное следствие: на второй день он переползет из четвертого ящика в ящик 3 или ящик 5. Достаточно проверить будку номер 3 — он окажется или там, или нет (тогда он в будке 5). И если он в будке 5, то на третий день достаточно проверить ящик 4, ибо других вариантов для мишки не останется.
Важно: таким образом, если медведь изначально пребывал в четных ящиках, то нам достаточно будет по очереди проверить будки 2, 3 и 4. Медведь найден.
Шаг 2. Выстроим противоположную упрощенную модель. Предположим, будто медведь изначально затаился в нечетном ящике, то есть 1, 3 или 5.
Из этих будок не так уж и много путей. 1 и 5 — крайние будки, так что, как ни крути, но на второй день медведь переберется в будку 2 или 4. На третий день мишка будет в будке 1, 3 или 5. А на четвертый — в 2 или 4. Фактически мы возвращаемся к шагу 1!
Шаг 3. Итоговый
1 день — проверяем ящик 2
2 день — проверяем ящик 3
3 день — проверяем ящик 4
Если за три дня медведь не локализован, то это был «нечетный медведь». И мы повторяем то же самое с четвертого дня.
4 день — проверяем ящик 2
5 день — проверяем ящик 3
6 день — проверяем ящик 4
На седьмой день хитрый медведь обязательно будет найден. И съеден либо он, либо хозяева. Ура!
