Стол, дырки и бокалы
Nov. 27th, 2011 11:30 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
kaipaВ книжке М.Гарднера прочитал любопытную задачу, и, гуляя с ребенком, которому сегодня исполнился ровно год, над ней поразмышлял. Задача простая, но необычная.
Представьте себе вращающийся стол с несколькими глубокими дырками, расположенными симметрично по краю. Например, круглый стол с четырьмя дырками. Дырки не сквозные, это как бы стакан, лунка, внутри которой помещается пустой бокал. Бокал не видно, его можно нащупать только опустив руку в дырку. Бокалы могут стоять на ножке, либо быть перевернутыми. Стол свободно вращается, и абсолютно симметричный. Игра, а это можно рассматривать как игру, начинается с некоторого положения стола и неизвестного расположения бокалов в лунках. Какие-то бокалы стоят, какие-то перевернуты. Известно только, что не все они в одинаковом положении. На каждом ходу игрок может опустить обе руки в любые две произвольные лунки, нащупать бокалы и, если сочтет нужным, перевернуть один или оба. Если все бокалы оказываются в одинаковом положении -- звенит звонок, игра закончена. Иначе игра продолжается. Перед каждым следующим ходом стол очень быстро вращается произвольным образом, и останавливается в случайном положении. В этом вся сложность: игрок не знает, какие лунки он "проверял" на предыдущем ходу. Задача игры -- привести все бокалы в одинаковое положение за минимальное число шагов.
Для случая двух лунок решение тривиальное, трех -- простое. Четырех -- стоит подумать, это и есть основной вопрос задачи. И дополнительный -- доказать, что для пяти и более лунок, не существует стратегии, которая приводит к выигрышу за конечное число шагов.
Комментарии отключены, чтобы не лишать удовольствия подумать над задачей самостоятельно. Если будут какие-то вопросы и уточнения в условие, то я обновлю пост.
Первому, кто правильно ответит, по примеру уважаемого![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
falcao передается эстафета на интересную задачу.
fregimus первым решил задачу, сначала не совсем оптимально, но потом улучшил решение. На дополнительный вопрос у меня такие же соображения, и они кажутся вполне строгими.
fat_crocodile решил задачу вторым и последним.
Надеюсь, задачка понравилась.
Представьте себе вращающийся стол с несколькими глубокими дырками, расположенными симметрично по краю. Например, круглый стол с четырьмя дырками. Дырки не сквозные, это как бы стакан, лунка, внутри которой помещается пустой бокал. Бокал не видно, его можно нащупать только опустив руку в дырку. Бокалы могут стоять на ножке, либо быть перевернутыми. Стол свободно вращается, и абсолютно симметричный. Игра, а это можно рассматривать как игру, начинается с некоторого положения стола и неизвестного расположения бокалов в лунках. Какие-то бокалы стоят, какие-то перевернуты. Известно только, что не все они в одинаковом положении. На каждом ходу игрок может опустить обе руки в любые две произвольные лунки, нащупать бокалы и, если сочтет нужным, перевернуть один или оба. Если все бокалы оказываются в одинаковом положении -- звенит звонок, игра закончена. Иначе игра продолжается. Перед каждым следующим ходом стол очень быстро вращается произвольным образом, и останавливается в случайном положении. В этом вся сложность: игрок не знает, какие лунки он "проверял" на предыдущем ходу. Задача игры -- привести все бокалы в одинаковое положение за минимальное число шагов.
Для случая двух лунок решение тривиальное, трех -- простое. Четырех -- стоит подумать, это и есть основной вопрос задачи. И дополнительный -- доказать, что для пяти и более лунок, не существует стратегии, которая приводит к выигрышу за конечное число шагов.
Комментарии отключены, чтобы не лишать удовольствия подумать над задачей самостоятельно. Если будут какие-то вопросы и уточнения в условие, то я обновлю пост.
Первому, кто правильно ответит, по примеру уважаемого
falcao передается эстафета на интересную задачу.fregimus первым решил задачу, сначала не совсем оптимально, но потом улучшил решение. На дополнительный вопрос у меня такие же соображения, и они кажутся вполне строгими.fat_crocodile решил задачу вторым и последним. Надеюсь, задачка понравилась.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2011-11-28 07:39 pm (UTC)И в случае трех, и четырех лунок есть вполне конкретные стратегии игры, приводящие к выигрышу за конечное число шагов даже при тотальном невезении. В этом-то и весь интерес задачки :)
no subject
Date: 2011-11-28 07:43 pm (UTC)Идея в том, что состояние два-на-два очень быстро доводится до конца. Если у нас два-на-два и одинаковые расположены по диагонали, то в один ход: берём, любую диагональ и переворачиваем.
Если одинаковые -- соседние, то один или два хода: берём пару соседних, если они одиаковые, переворачиваем -- готово. Если они разные, тоже переворачиваем оба, почле чего получаем одинаковые пары по диагонали.
Теперь надо привести всё к два-на-два.
Берём два соседних, устанавливаем их вверх.
Берём два диагональных, устанавливаем вверх.
Если не конец, то у нас три-на-один.
Берём два соседних,
-- если один из них вниз -- переворачиваем его вверх, конец.
-- если оба вверх, любой из них переворачиваем вниз. Получили два-на-два, но не известно в какой позиции.
Берём два диагональных.
- если они одинаковые, то одинаковые по диагонали, переворачиваем их, конец.
- если они разные, то одинаковые соседние, не трогаем их, действуем по соотв. алгоритму.
---
Для трёх победа на втором ходе, там это просто понятно.
no subject
Date: 2011-11-29 07:55 am (UTC)