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

[kaipa]

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

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

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

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

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

---

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

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

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

Comments

[ushastyi.livejournal.com]

Да. Объявляю Вас победителем. Участников, впрочем, было всего два. Буду скоро в Bay Area, могу какой-нибудь приз привезти :)

[fregimus.livejournal.com]

Я подумаю над задачкой по эстафете. Какой там приз, что Вы, мне было приятно голову поломать. Вам спасибо за задачку. Тут еще есть, кстати, над чем дальше подумать: если двумя руками нельзя, то можно ли тремя перевернуть 5 стаканов? А если 6 стаканов — сколько рук надо?

[ushastyi.livejournal.com]

Да, решение можно обобщить. Сколько надо рук для стола с N-лунками, чтобы было решение. Я не думал об этом.