Стол, дырки и бокалы
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 решил задачу вторым и последним. Надеюсь, задачка понравилась.
