Стол, дырки и бокалы

[kaipa]

В книжке М.Гарднера прочитал любопытную задачу, и, гуляя с ребенком, которому сегодня исполнился ровно год, над ней поразмышлял. Задача простая, но необычная.

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

Для случая двух лунок решение тривиальное, трех -- простое. Четырех -- стоит подумать, это и есть основной вопрос задачи. И дополнительный -- доказать, что для пяти и более лунок, не существует стратегии, которая приводит к выигрышу за конечное число шагов.

Комментарии отключены, чтобы не лишать удовольствия подумать над задачей самостоятельно. Если будут какие-то вопросы и уточнения в условие, то я обновлю пост.

Первому, кто правильно ответит, по примеру уважаемого falcao передается эстафета на интересную задачу.

---

fregimus первым решил задачу, сначала не совсем оптимально, но потом улучшил решение. На дополнительный вопрос у меня такие же соображения, и они кажутся вполне строгими.

fat_crocodile решил задачу вторым и последним.

Надеюсь, задачка понравилась.

Comments

[fregimus.livejournal.com]

А информация о взаимном расположении лунок сохраняется, т. е. я могу пользоваться знанием, что я перед этим переворачивал две соседние лунки, или что они были на диаметре?

Второй вопрос — бокалы нащупываются после того, как обе лунки выбраны, т. е. можно сначала засунуть одну руку, пощупать, а потом выбрать вторую лунку?

[ushastyi.livejournal.com]

1. Да, конечно. Вы помните все, что вы делали.
2. Сначала выбираются лунки, а потом засовываются руки.