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

[kaipa]

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

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

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

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

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

---

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

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

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

Comments

[fat-crocodile.livejournal.com]

Я правильно понял, что мысль в том, что последовательность "случайных положений" может оказаться такой, что какая-то лунка так никогда и не попадёт под руку?

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

Видимо я всё-таки что-то понял неправильно :)

[ushastyi.livejournal.com]

Я открыл комментарий, потому что это вопрос по условию.

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

[fregimus.livejournal.com]

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

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

[ushastyi.livejournal.com]

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

[fregimus.livejournal.com]

У меня получилось решение в 6 шагов для 4 стаканов. Сейчас опишу.

Пусть лунки (а они в углах квадрата) поворачиваются к нам стороной. Пронумеруем их, как будто поля левого нижнего угла шахматной доски. Проверять и переворачивать всегда будем либо a1 и a2, и тогда буду говорить «горизонталь», либо a1 и b2, и это я буду обозначать словом «диагональ».

1. Переворачиваем горизонталь донцами вверх.

2. Переворачиваем диагональ донцами вверх.

3. Поскольку игра не кончилась, имеется один стакан донцем вниз. Проверяем горизонталь. Если имеется стакан донцем вниз, то переворачиваем его, и получаем решение. Если же оба донцами вверх, переворачивам любой. После этого имеем одну из двух позиций:

XO XO
OX XO

где X означает стакан донцем вниз, а O — донцем вверх.

4. Проверяем любую диагональ. Если стаканы одинаковые, переворачиваем их, чем решаем задачу. Если же нет, ничего не переворачиваем. Теперь известно, что позиция правая из деух описанных.

5. Переворачиваем горизонталь не глядя. Если стаканы одинаковые, то это будет решением. В противном случае, позиция превратится в диагональную. Ниже 4 возможные поворота позиции до перестановки стаканов

XO XX OX OO
XO OO OX XX

и соответствующие после

XO XX OX OO
OX XX XO OO

2 и 4 являются решениями. Позиции 1 и 3 симметричны, и по диагонали находятся стаканы разной ориентации, так что

6. переворачиваем диагональ, и это приводит к решению.

У меня 4 утра, а я дремлю и сквозь сон решаю Ваши задачки… Кстати, вот набросок доказательства к тому, что 5 стаканов за ограниченное время не переворачиваются. Гипотеза в том, что при любой стратегии возможны 2 стакана, до которых мы никогда не дотронемся, и, если они ориентированны по-разному, то и не придем к решению. Кажется очевидным, что это так, но формально мне не удается свести это к известным свойствам групп. В полусне, во всяком случае, — буду дальше эту задачку спать думать.

[fat-crocodile.livejournal.com]

Для двух сразу понятно, просто повернуть в одну сторону.

Для трёх очевидно: если оба в одну сторону, перевернуть их, если в разные, то все вверх, повторять до победы.

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

Для пяти, если не везёт, можно так никогда и не добраться до двух лунок, понятно, что тогда ничего не получится.

[fregimus.livejournal.com]

А можно ж и за 5 шагов:

3. Проверяем диагональ. Если имеется стакан донцем вниз, то переворачиваем его, и получаем решение. Если же оба донцами вверх, переворачивам любой. Переходим сразу к п. 5.

[ushastyi.livejournal.com]

"Повторять до победы" -- это не очень хороший ответ. А вдруг победы не будет? :)
И в случае трех, и четырех лунок есть вполне конкретные стратегии игры, приводящие к выигрышу за конечное число шагов даже при тотальном невезении. В этом-то и весь интерес задачки :)

[fat-crocodile.livejournal.com]

ага, алгоритм для четырёх.

Идея в том, что состояние два-на-два очень быстро доводится до конца. Если у нас два-на-два и одинаковые расположены по диагонали, то в один ход: берём, любую диагональ и переворачиваем.
Если одинаковые -- соседние, то один или два хода: берём пару соседних, если они одиаковые, переворачиваем -- готово. Если они разные, тоже переворачиваем оба, почле чего получаем одинаковые пары по диагонали.

Теперь надо привести всё к два-на-два.

Берём два соседних, устанавливаем их вверх.
Берём два диагональных, устанавливаем вверх.
Если не конец, то у нас три-на-один.
Берём два соседних,
-- если один из них вниз -- переворачиваем его вверх, конец.
-- если оба вверх, любой из них переворачиваем вниз. Получили два-на-два, но не известно в какой позиции.
Берём два диагональных.
- если они одинаковые, то одинаковые по диагонали, переворачиваем их, конец.
- если они разные, то одинаковые соседние, не трогаем их, действуем по соотв. алгоритму.

---

Для трёх победа на втором ходе, там это просто понятно.

[ushastyi.livejournal.com]

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

[ushastyi.livejournal.com]

Засчитано.

[fregimus.livejournal.com]

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

[fat-crocodile.livejournal.com]

о, до этого я не догадался, только до 6-шагового.

[ushastyi.livejournal.com]

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