Пазл «Четыре стакана»
? обозначают очки в любом состоянии: лицевой стороной вверх или вниз . Галочки обозначают решенные аранжировки. На каждом этапе показаны только отдельные договоренности.
На шаге 3, если стакан стоит лицевой стороной вниз, он переворачивается лицевой стороной вверх; в противном случае любое стекло переворачивается лицевой стороной вниз.
Головоломка с четырьмя стаканами , также известная как задача слепого бармена . [1] — логическая головоломка, впервые опубликованная Мартином Гарднером в его колонке «Математические игры» в февральском выпуске журнала Scientific American за 1979 год . [2]
Головоломка
[ редактировать ]Четыре стакана или стакана расставляют по углам квадрата Ленивой Сьюзен . Некоторые стаканы стоят вертикально (вверх), а некоторые перевернуты (вниз). Человека с завязанными глазами усаживают рядом с Ленивой Сьюзен, и он должен переставить очки так, чтобы они были либо подняты, либо опущены, причем любое расположение приемлемо, о чем будет сигнализировать звон колокольчика. Стаканы можно переставлять по очереди при соблюдении следующих правил. Любые два стекла можно осмотреть за один ход, и, почувствовав их ориентацию, человек может изменить ориентацию одного из них, ни одного из них или обоих. После каждого поворота Ленивая Сьюзен поворачивается на случайный угол. Задача состоит в том, чтобы разработать алгоритм, который позволил бы человеку с завязанными глазами обеспечить, чтобы все очки имели одинаковую ориентацию (вверх или вниз) за конечное число поворотов. Алгоритм должен быть нестохастическим, т.е. не зависеть от удачи. [3]
Решение
[ редактировать ]Алгоритм, гарантирующий, что звонок прозвенит не более пяти ходов, следующий: [2]
- На первом ходу выберите пару очков, противоположных по диагонали, и поверните оба стекла вверх.
- На втором ходу выберите два соседних стакана. По крайней мере один из них будет активен в результате предыдущего шага. Если другой не работает, включите и его. Если звонок не прозвенит, значит, теперь три стакана вверху и один внизу.
- На третьем ходу выберите пару очков, противоположных по диагонали. Если один из них не работает, включите его, и звонок зазвенит. Если оба включены, выключите один. Теперь внизу два стакана, и они должны быть рядом.
- На четвертом ходу выберите два соседних стакана и поменяйте местами оба. Если оба были в одной ориентации, то прозвенит звонок. В противном случае теперь осталось два стакана, и они должны находиться по диагонали напротив.
- На пятом ходу выберите пару очков, противоположных по диагонали, и поменяйте их местами. Колокольчик прозвенит.
Обобщения
[ редактировать ]Загадку можно обобщить до n очков вместо четырех. Для двух стаканов задача решается тривиально за один ход, переворачивая любой из стаканов. На три стакана действует двухоборотный алгоритм. Для пяти и более стаканов не существует алгоритма, гарантирующего, что звонок прозвенит за конечное число ходов. [2]
Дальнейшее обобщение позволяет k очков (вместо двух) из n проверять на каждом ходу. Можно найти алгоритм, позволяющий звонить в колокольчик за конечное число ходов, пока k ≥ (1 - 1/ p ) n , где p — наибольший простой делитель числа n . [2]
Ссылки
[ редактировать ]- ^ Эренборг, Ричард ; Скиннер, Крис (1995). «Проблема слепого бармена» (PDF) . Журнал комбинаторной теории, серия А. 70 (2): 249–266. дои : 10.1016/0097-3165(95)90092-6 .
- ^ Jump up to: а б с д * Хэвил, Джулиан (2007). «Глава 4: Вращение стола». В замешательстве! . Издательство Принстонского университета. ISBN 978-0-691-12056-0 .
- ^ «Брейнгл » Логическая головоломка «Четыре стакана» .