green_fr (green_fr) wrote,
green_fr
green_fr

Category:

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

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


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

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

  • La Vague и L'Odyssée des Gènes

    Практически одновременно купил два нон-фикшена. La Vague — книга французского эпидемиолога о первой волне ковида. Мы с Анютой — она тоже прочитала…

  • Разные книжки

    Был период, когда читать хотелось совсем какую-то ерунду, лишь бы попроще. Похоже, период прошёл, но за это время успел прочитать: «Nymphéas noirs»…

  • Weapons of Math Destruction

    Прочитал (спасибо wildest_honey!) книжку про риски применения математических алгоритмов в разных областях. Автор вводит вынесенный…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 74 comments

  • La Vague и L'Odyssée des Gènes

    Практически одновременно купил два нон-фикшена. La Vague — книга французского эпидемиолога о первой волне ковида. Мы с Анютой — она тоже прочитала…

  • Разные книжки

    Был период, когда читать хотелось совсем какую-то ерунду, лишь бы попроще. Похоже, период прошёл, но за это время успел прочитать: «Nymphéas noirs»…

  • Weapons of Math Destruction

    Прочитал (спасибо wildest_honey!) книжку про риски применения математических алгоритмов в разных областях. Автор вводит вынесенный…