Задача о четырёх стаканах
Задача о четырёх стаканах[1] — логическая головоломка Мартина Гарднера. Опубликована в колонке «Математические игры» февральского выпуска журнала Scientific American за 1979 год.
Формулировка править
Четыре стакана расположены по углам квадратного крутящегося столика. Некоторые стаканы поставлены вверх (то есть правильно), а некоторые вниз (то есть перевернуты). Человек с завязанными глазами должен переставить стаканы так, чтобы все они были в одном положении, в этом случае прозвенит колокольчик. Стаканы могут быть переставлены по очереди в соответствии со следующими правилами. Любые два стакана могут быть проверены за один ход, и, почувствовав их ориентацию, человек может изменить ориентацию любого из них, ни одного или обоих стаканов. После каждого поворота столик поворачивается на случайный угол. Задача состоит в том, чтобы разработать алгоритм, который позволит человеку с завязанными глазами убедиться, что все стаканы имеют одинаковую ориентацию (вверх или вниз) за конечное число поворотов. Алгоритм должен быть нестохастическим, то есть он не должен зависеть от удачи.[2]
Решение править
Алгоритм, гарантирующий, что звонок прозвенит не более чем через пять оборотов, выглядит следующим образом:[3]
- На первом повороте выберите по диагонали противоположную пару стаканов и переверните оба стакана вверх.
- На втором повороте выберите два соседних стакана. По крайней мере один из них стоит вверх в результате предыдущего шага. Если другой стоит вниз, переверните его тоже. Если звонок не прозвенит, то теперь три стакана стоят вверх и один вниз.
- На третьем повороте выберите по диагонали противоположную пару стаканов. Если один из них стоит вниз, переверните его, и зазвенит звонок. Если оба вверх, переверните один. Теперь два стакана поставлены вниз, и они стоят рядом.
- На четвертом повороте выберите два соседних стакана и переверните оба. Если оба были в одной и той же ориентации, то прозвенит звонок. В противном случае теперь два стакана перевёрнуты, и они должны быть по диагонали друг от друга.
- На пятом повороте выберите по диагонали противоположную пару стаканов и переверните оба. Прозвенит звонок.
Обобщения править
Головоломку можно обобщить на n стаканов вместо четырех. Для двух стаканов это тривиально решается за один ход путем переворачивания любого стакана. Для трёх стаканов существует алгоритм в два оборота. Для пяти и более стаканов не существует алгоритма, гарантирующего, что колокольчик зазвонит за конечное число оборотов.[4]
Дальнейшее обобщение позволяет проверять k стаканов (вместо двух) из n стаканов на каждом повороте. Можно найти алгоритм, решающий задачу за конечное число оборотов если k ≥ (1 − 1/p)n, где p — наибольший простой множитель n.[4]
Примечания править
- ↑ Ehrenborg, Richard (1995). "The Blind Bartender's Problem" (PDF). Journal of Combinatorial Theory, Series A. 70 (2): 249—266. doi:10.1016/0097-3165(95)90092-6. Архивировано (PDF) из оригинала 13 августа 2021. Дата обращения: 14 ноября 2021.
- ↑ Braingle » 'Four glasses' Brain Teaser. Дата обращения: 14 ноября 2021. Архивировано 14 ноября 2021 года.
- ↑ Havil, Julian. Chapter 4: The Spin of a Table // Nonplussed!. — Princeton University Press, 2007. — ISBN 978-0-691-12056-0.Havil, Julian (2007). "Chapter 4: The Spin of a Table".
- ↑ 1 2 Havil, Julian. Chapter 4: The Spin of a Table // Nonplussed!. — Princeton University Press, 2007. — ISBN 978-0-691-12056-0.Havil, Julian (2007). "Chapter 4: The Spin of a Table". Nonplussed!. Princeton University Press. ISBN 978-0-691-12056-0.