Головоломка с четырьмя очками - Four glasses puzzle - Wikipedia

В пазл с четырьмя очками, также известный как проблема слепого бармена,[1] логическая головоломка, впервые опубликованная Мартин Гарднер в его колонке «Математические игры» в февральском выпуске журнала Scientific American.[2]

Головоломка

По углам квадрата ставят четыре стакана или стакана. Ленивая Сьюзан. Некоторые очки стоят вертикально (вверх), а некоторые - вверх дном (вниз). Человек с завязанными глазами сидит рядом с Ленивой Сьюзен, и ему требуется переставить очки так, чтобы все они были вверху или полностью опущены, любое расположение приемлемо, о чем будет сигнализировать звон колокольчика. Переставлять стаканы можно по очереди при соблюдении следующих правил. Любые два очка можно осмотреть за один ход, и, почувствовав их ориентацию, человек может изменить ориентацию одного, ни одного или обоих очков. После каждого поворота Ленивая Сьюзен поворачивается на случайный угол. Задача состоит в том, чтобы разработать алгоритм, который позволяет человеку с завязанными глазами гарантировать, что все очки имеют одинаковую ориентацию (вверх или вниз) за конечное число оборотов. Алгоритм должен быть нестохастическим, т.е. не должен зависеть от удачи.[3]

Решение

Алгоритм, гарантирующий, что звонок прозвенит не более пяти оборотов, следующий:[2]

  1. На первом повороте выберите диагонально противоположную пару очков и переверните оба стакана вверх.
  2. На втором ходу выберите два соседних стакана. По крайней мере, один будет поднят в результате предыдущего шага. Если другой не работает, включите и его. Если звонок не звонит, то теперь три стакана вверху и один внизу.
  3. На третьем повороте выберите диагонально противоположные очки. Если один из них не работает, включите его, и раздастся звонок. Если оба поднялись, убавьте один. Теперь внизу два стакана, и они должны быть рядом.
  4. На четвертом повороте выберите два соседних стакана и поменяйте местами оба. Если бы оба были в одной ориентации, звонок прозвенит. В противном случае теперь есть два стакана вниз, и они должны быть противоположны по диагонали.
  5. На пятом повороте выберите диагонально противоположную пару очков и переверните оба. Колокол зазвонит.

Обобщения

Загадку можно обобщить на п стаканы вместо четырех. Для двух стаканов это тривиально решается за один оборот, переворачивая любое стекло. Для трех стаканов действует двухоборотный алгоритм. Для пяти и более очков не существует алгоритма, который гарантировал бы, что звонок прозвенит за конечное число оборотов.[2]

Дальнейшее обобщение позволяет k очки (вместо двух) из п Очки проверять на каждом шагу. Можно найти алгоритм, который звонит в колокол за конечное число оборотов, пока k ≥ (1 − 1/п)п куда п является наибольшим основным фактором п.[2]

Рекомендации

  1. ^ Эренборг, Ричард; Скиннер, Крис (1995). "Проблема слепого бармена" (PDF). Журнал комбинаторной теории, серия А. 70 (2): 249–266. Дои:10.1016/0097-3165(95)90092-6.
  2. ^ а б c d *Хэвил, Джулиан (2007). «Глава 4: Вращение стола». В замешательстве!. Издательство Принстонского университета. ISBN  978-0-691-12056-0.
  3. ^ http://www.braingle.com/brainteasers/8758/four-glasses.html

http://puzzlersworld.com/interview-puzzles/four-glasses-on-a-square-table/