как стать умнее кошки

green-fr — 04.07.2017 Интересная задачка:
Перед вами семь дверей. За одной из них сидит кошка.
Каждый день вы можете открыть и закрыть одну дверь. Если кошка сидит за ней – вы победили.
Если бы кошка все время сидела за какой-то одной дверью, вы бы гарантировано нашли ее за семь попыток. Точнее – даже за шесть попыток.
Но каждую ночь кошка сдвигается на одну дверь – либо влево, либо вправо. Как ей захочется (понятно, что из крайней левой двери она может сдвинуться только направо, а из крайней правой – только налево).
Как вам найти кошку?

Подмывает ответить, что нет решения, но хочется его и поискать.
1. Открывать двери случайно, благо (6/7)^n очень быстро сходится к нулю при n уходящем в бесконечность. Но гарантии нет.
2. Стоять на центральной позиции — наличие стенок склоняет кошку к центральной двери, ну и вообще среднее отклонение от первоначальной позиции со временем растёт. То же, что и п.1.
3. Альтернативно прочитать правила. «Каждый день вы можете открыть и закрыть одну дверь» — я могу закрыть дверь после того, как я её открыл, или обязан (то есть «открыть и закрыть» идёт в комплекте)? Но эта веточка лично мне не интересна.
4. Как-то играть на чётности / нечётности? Грубо говоря, если мы можем открыть сразу три двери, то открываем все чётные. Если там кошки нет, то она там появится на следующем же ходу. Если бы у нас было две двери, то можно было бы открыть две чётные, а потом те две нечётные, которые были вокруг оставшейся чётной. Таким образом, мы нашли бы кошку, если бы в начале она сидела за чётной дверью. Значит, она была за нечётной — аналогично решаем задачу с 4 нечетными дверьми. Но как перейти к одной двери?

Update: в комментах есть решение за 10 ходов, неправильное, но за 6 и сложное, но красивое за 9 :-)

Оставить комментарий

Популярные посты:

• Ранее
• Архив