Петриковский десант
- 1 year ago
- 0
- 0
Задача о четырёх стаканах — логическая головоломка Мартина Гарднера . Опубликована в колонке «Математические игры» февральского выпуска журнала Scientific American за 1979 год.
Четыре стакана расположены по углам квадратного крутящегося столика. Некоторые стаканы поставлены вверх (то есть правильно), а некоторые вниз (то есть перевернуты). Человек с завязанными глазами должен переставить стаканы так, чтобы все они были в одном положении, в этом случае прозвенит колокольчик. Стаканы могут быть переставлены по очереди в соответствии со следующими правилами. Любые два стакана могут быть проверены за один ход, и, почувствовав их ориентацию, человек может изменить ориентацию любого из них, ни одного или обоих стаканов. После каждого поворота столик поворачивается на случайный угол. Задача состоит в том, чтобы разработать алгоритм, который позволит человеку с завязанными глазами убедиться, что все стаканы имеют одинаковую ориентацию (вверх или вниз) за конечное число поворотов. Алгоритм должен быть нестохастическим, то есть он не должен зависеть от удачи.
Алгоритм, гарантирующий, что звонок прозвенит не более чем через пять оборотов, выглядит следующим образом:
Головоломку можно обобщить на n стаканов вместо четырех. Для двух стаканов это тривиально решается за один ход путем переворачивания любого стакана. Для трёх стаканов существует алгоритм в два оборота. Для пяти и более стаканов не существует алгоритма, гарантирующего, что колокольчик зазвонит за конечное число оборотов.
Дальнейшее обобщение позволяет проверять k стаканов (вместо двух) из n стаканов на каждом повороте. Можно найти алгоритм, решающий задачу за конечное число оборотов если k ≥ (1 − 1/ p ) n , где p — наибольший простой множитель n .