Игра Берлекэмпа с переключением

Игра Берлекэмпа с переключением — математическая игра, предложенная американским математиком Элвином Берлекэмпом . ^[1] Ее также назвали игрой переключения Гейла-Берлекэмпа в честь Дэвида Гейла , который открыл ту же игру независимо. ^[2] или игра «Дисбаланс света» . ^[3] Он включает в себя систему лампочек , управляемую двумя блоками переключателей: один игрок пытается включить как можно больше лампочек, а другой пытается выключить как можно больше лампочек. Его можно использовать для демонстрации концепции радиуса покрытия в теории кодирования .

Правила [ править ]

Оборудование для игры состоит из комнаты, содержащей прямоугольный ряд лампочек размером $a\times b$ для некоторых номеров $a$ и $b$ . Банк $ab$ выключатели на одной стороне комнаты управляют каждой лампочкой индивидуально. При щелчке одного из этих переключателей его лампочка переключается с выключенного состояния на включенное или с включенного на выключенное, в зависимости от его предыдущего состояния. На другой стороне комнаты находится еще один банк $a+b$ выключатели, по одному на каждый ряд или столбец лампочек. При каждом повороте любого из этих переключателей каждая лампочка в строке или столбце, которой он управляет, переключается с выключенного состояния на включенное или с включенного на выключенное, в зависимости от ее предыдущего состояния. При нажатии более чем одного переключателя порядок, в котором переключаются переключатели, не влияет на результат: одни и те же лампочки будут гореть в конце последовательности переключений, независимо от того, в каком порядке они были перевернуты.

Игра проводится в два раунда. В первом раунде первый игрок использует переключатели, управляющие отдельными источниками света, чтобы произвольно включать или выключать свет. Во втором раунде второй игрок использует переключатели, которые управляют рядами или столбцами огней, изменяя узор огней, установленный первым игроком, на другой узор (или, возможно, оставляя его неизменным). Цель первого игрока — чтобы к концу игры оставалось горящим как можно больше огней, а цель второго игрока — чтобы горело как можно меньше огней. Следовательно, первый игрок должен выбрать схему освещения, при которой второй игрок не сможет выключить большое количество источников света.

История [ править ]

Берлекамп работал в Bell Labs в Мюррей-Хилл, штат Нью-Джерси, с 1966 по 1971 год. ^[4] Там он сконструировал физический экземпляр этой игры для случая. $10\times 10$ в общей комнате математического факультета. ^[1]^[2] Дэвид Гейл также изобрел эту игру независимо незадолго до 1971 года. ^[5]

Ранние исследования по смежным проблемам включали публикации Эндрю М. Глисона ( 1960 ), чьи компьютерные эксперименты можно интерпретировать как вопрос о том, $15\times 15$ игре, насколько хорошо второй игрок может справиться с первым игроком, который играет случайным образом, ^[6] и Дж. Мун и Лео Мозер ( 1966 ), которые теоретически решают вопрос Глисона и показывают, что почти для всех выборов первого игрока в пределе больших размеров игрового поля оптимальная ценность игры близка к ${\tfrac {1}{2}}n^{2}$ . ^[7]

Анализ [ править ]

Математически огни, включенные в результате хода первого игрока, можно описать как набор $S$ , а наименьшее количество огней, которое может быть достигнуто при лучшей игре второго игрока, как число $f(S)$ . Лучший ход для первого игрока – выбрать сет. $S$ это максимизирует $f(S)$ . Следовательно, наибольшее количество огней, которого можно достичь при наилучшей игре для первого игрока, можно описать как число ${\textstyle R_{a,b}=\max _{S}f(S)}$ . Помимо вопроса о том, как хорошо играть в отдельной игре, существует более широкий вопрос, ставший объектом математических исследований: охарактеризовать ценность $R_{a,b}$ вообще, как функция $a$ и $b$ , чтобы определить его поведение как функцию или вычислить его значение для как можно большего числа комбинаций $a$ и $b$ насколько это возможно.

Случай с квадратом $n\times n$ массив был решен для $n\leq 12$ . Кроме того, нижние границы для $R_{n,n}$ были найдены для $n\leq 20$ . ^[8]^[9]^[10]^[11] Эти цифры:

Решения для $n\times n$
$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
$R_{n,n}$	0	1	2	4	7	11	16	22	27	35	43	54	≥ 60	≥ 71	≥ 83	≥ 96	≥ 107	≥ 122	≥ 139	≥ 148

Асимптотически эти числа растут как ${\tfrac {n^{2}}{2}}-\Theta (n^{3/2})$ . ^[2]^[5]^[12]

Вычислительная сложность [ править ]

Поскольку существует экспоненциально много вариантов, для которых переключаются переключатели, исчерпывающий поиск оптимального выбора невозможен для больших $n$ , ставя вопрос о том, насколько хорошо игроки с ограниченными вычислительными возможностями могут играть в эту игру.

Первый игрок может сделать ожидаемую ценность игры равной ${\tfrac {n^{2}}{2}}-O(n^{3/2})$ играя в случайном порядке. Аналогично, второй игрок может получить значение, ожидаемое расстояние которого от ${\tfrac {n^{2}}{2}}$ является $\Omega (n^{3/2})$ играя в случайном порядке; это значение может быть больше или меньше, чем ${\tfrac {n^{2}}{2}}$ , но если оно больше, второй игрок может перевернуть все переключатели строк, чтобы получить значение, меньшее на ту же величину. ^[2]^[5]^[12] Эту случайную стратегию для второго игрока можно сделать неслучайной, используя метод условных вероятностей , давая алгоритм с полиномиальным временем , который получает те же гарантии значения решения. Другая дерандомизация дает параллельный алгоритм в классе сложности NC . ^[13]

Поиск оптимального выбора для второго игрока в игре, когда первый игрок выбрал, какие лампочки зажигать, является NP-сложной задачей. ^[14] Однако существует схема аппроксимации с полиномиальным временем для $n\times n$ игра, которая может найти выбор для второго игрока, который оставляет только $(1+\varepsilon )$ раз минимально возможное количество зажженных лампочек, для любого $\varepsilon >0$ , во времени $O(n^{2})+2^{O(1/\varepsilon ^{2})}$ . ^[15]

с кодирования Связь теорией

Игра Берлекэмпа с переключением может использоваться в теории кодирования как демонстрация радиуса покрытия определенного двоичного линейного кода . Двоичный линейный код длины $n$ и размер $d$ определяется как $d$ -мерное линейное подпространство $n$ -мерное векторное пространство $\mathbb {F} _{2}^{n}$ над конечным полем с двумя элементами , $\mathbb {F} _{2}$ . Элементы подпространства называются кодовыми словами, а радиус покрытия — наименьшим числом. $r$ так, что каждая точка $\mathbb {F} _{2}^{n}$ находится на расстоянии Хэмминга $r$ кодового слова.

Позволять $n=ab$ и $d=a+b-1$ . Для этих значений параметров векторное пространство $\mathbb {F} _{2}^{n}$ описывает все возможные узоры горящих лампочек на $a\times b$ массив лампочек с операцией сложения векторов, которая объединяет два шаблона, зажигая лампочки, которые появляются ровно в одном из двух шаблонов ( операция симметричной разности для наборов горящих лампочек). Можно определить линейное подпространство, состоящее из всех шаблонов, которые второй игрок может полностью отключить, или, что эквивалентно, из всех шаблонов, которые второй игрок может создать, начиная с полностью отключенной доски. Хотя у второго игрока есть $2^{a+b}$ выбор того, как установить второй блок переключателей, в этом подпространстве есть $2^{a+b-1}$ элементы, придающие ему размерность $a+b-1$ , потому что переключение всех переключателей второго игрока не влияет на рисунок горящих лампочек.

Затем $R_{a,b}$ — радиус покрытия этого кода. Набор зажженных лампочек, выбранный первым игроком с лучшей игрой, дает очко $\mathbb {F} _{2}^{n}$ это максимально далеко от линейного подпространства. Набор лампочек, состояние которых изменено вторым игроком при лучшей игре, дает ближайшую точку в линейном подпространстве. Набор лампочек, которые остаются гореть после этого выбора, — это те, число которых определяет расстояние Хэмминга между этими двумя точками. ^[1]

См. также [ править ]

Lights Out (игра) — другая головоломка, включающая выключение лампочек с помощью переключателей, управляющих несколькими лампочками.

Ссылки [ править ]

^ Jump up to: Перейти обратно: ^а ^б ^с Слоан, Нью-Джерси (1987). «Нерешенные проблемы, связанные с радиусом покрытия кодов». В обложке, Томас М .; Гопинатх, Б. (ред.). Открытые проблемы коммуникации и вычислений . Нью-Йорк: Спрингер. стр. 51–56. дои : 10.1007/978-1-4612-4808-8_11 .
^ Jump up to: Перейти обратно: ^а ^б ^с ^д Спенсер, Джоэл (1994). «Лекция 6: Хаос из порядка» . Десять лекций по вероятностному методу . Серия региональных конференций CBMS-NSF по прикладной математике. Том. 64 (Второе изд.). Филадельфия, Пенсильвания: Общество промышленной и прикладной математики. стр. 45–50. дои : 10.1137/1.9781611970074 . ISBN 0-89871-325-0 . МР 1249485 .
^ Араужо, Густаво; Пеллегрино, Даниэль (2019). «Задача перестановки Гейла – Берлекампа в более высоких измерениях». Европейский журнал комбинаторики . 77 : 17–30. arXiv : 1801.09194 . дои : 10.1016/j.ejc.2018.10.007 . МР 3872901 . S2CID 57760841 .
^ Сандерс, Роберт (18 апреля 2019 г.). «Элвин Берлекамп, теоретик игр и пионер программирования, умер в возрасте 78 лет» . Новости Беркли . Калифорнийский университет, Беркли.
^ Jump up to: Перейти обратно: ^а ^б ^с Браун, Томас А.; Спенсер, Джоэл Х. (1971). «Минимизация $\pm 1$ матрицы при сдвигах строк» . Colloquium Mathematicum . 23 : 165–171, 177. doi : 10.4064/cm-23-1-165-171 . MR 0307944 .
^ Глисон, Эндрю М. (1960). «Проблема поиска в $n$ -куб». В Беллман, Ричард ; Холл, Маршалл младший (ред.). Комбинаторный анализ . Труды симпозиумов по прикладной математике. Том 10. Провиденс, Род-Айленд: Американское математическое общество. стр. 175–178. MR 0114323 .
^ Мун, Дж.В.; Мозер, Л. (1966). «Экстремальная задача теории матриц» . Математический весник . 3(18) (37): 209–211. МР 0207570 .
^ Карлсон, Джордан; Столарски, Дэниел (октябрь 2004 г.). «Правильное решение игры Берлекэмпа с переключением» . Дискретная математика . 287 (1–3): 145–150. дои : 10.1016/j.disc.2004.06.015 . МР 2094708 .
^ Слоан, Нью-Джерси (ред.). «Последовательность A005311 (Решение игры Берлекампа с переключением (или игры с лампочкой) на доске n X n)» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
^ Пеллегрино, Д.; Рапосо-младший, А. (2022). «Константы неравенства Кахане – Салема – Зигмунда, асимптотически ограниченные единицей». Журнал функционального анализа . 282 (2): 109293. arXiv : 2006.12892 . дои : 10.1016/j.jfa.2021.109293 . S2CID 231895733 .
^ Пеллегрино, Д.; Рапосо-младший, А. (2021). «Верхние оценки констант неравенства Беннета и игры с переключением Гейла-Берлекэмпа». arXiv : 2111.00445v3 [ math.CO ].
^ Jump up to: Перейти обратно: ^а ^б Комлос, Дж . ; Сулёк, М. (1970). «О сумме элементов $\pm 1$ матрицы». Комбинаторная теория и ее приложения, II (Proc. Colloq., Balatonfüred, 1969) . С. 721–728. MR 0299500 .
^ Бергер, Бонни (1997). «Метод четвертого момента». SIAM Journal по вычислительной технике . 26 (4): 1188–1207. дои : 10.1137/S0097539792240005 . МР 1460721 . S2CID 14313557 .
^ Рот, Рон М.; Вишванатан, Кришнамурти (2008). «О сложности декодирования кода Гейла – Берлекэмпа». Транзакции IEEE по теории информации . 54 (3): 1050–1060. дои : 10.1109/TIT.2007.915716 . МР 2445050 .
^ Карпински, Марек ; Шуди, Уоррен (2009). «Схемы аппроксимации линейного времени для игры Гейла – Берлекампа и связанные с ней задачи минимизации». В Митценмахере, Майкл (ред.). Материалы 41-го ежегодного симпозиума ACM по теории вычислений, STOC 2009, Бетесда, Мэриленд, США, 31 мая — 2 июня 2009 г. АКМ. стр. 313–322. arXiv : 0811.3244 . дои : 10.1145/1536414.1536458 .

[sloane-1] Jump up to: Перейти обратно: ^а ^б ^с Слоан, Нью-Джерси (1987). «Нерешенные проблемы, связанные с радиусом покрытия кодов». В обложке, Томас М .; Гопинатх, Б. (ред.). Открытые проблемы коммуникации и вычислений . Нью-Йорк: Спрингер. стр. 51–56. дои : 10.1007/978-1-4612-4808-8_11 .

[spencer-2] Jump up to: Перейти обратно: ^а ^б ^с ^д Спенсер, Джоэл (1994). «Лекция 6: Хаос из порядка» . Десять лекций по вероятностному методу . Серия региональных конференций CBMS-NSF по прикладной математике. Том. 64 (Второе изд.). Филадельфия, Пенсильвания: Общество промышленной и прикладной математики. стр. 45–50. дои : 10.1137/1.9781611970074 . ISBN 0-89871-325-0 . МР 1249485 .

[3] Араужо, Густаво; Пеллегрино, Даниэль (2019). «Задача перестановки Гейла – Берлекампа в более высоких измерениях». Европейский журнал комбинаторики . 77 : 17–30. arXiv : 1801.09194 . дои : 10.1016/j.ejc.2018.10.007 . МР 3872901 . S2CID 57760841 .

[4] Сандерс, Роберт (18 апреля 2019 г.). «Элвин Берлекамп, теоретик игр и пионер программирования, умер в возрасте 78 лет» . Новости Беркли . Калифорнийский университет, Беркли.

[brospe-5] Jump up to: Перейти обратно: ^а ^б ^с Браун, Томас А.; Спенсер, Джоэл Х. (1971). «Минимизация $\pm 1$ матрицы при сдвигах строк» . Colloquium Mathematicum . 23 : 165–171, 177. doi : 10.4064/cm-23-1-165-171 . MR 0307944 .

[6] Глисон, Эндрю М. (1960). «Проблема поиска в $n$ -куб». В Беллман, Ричард ; Холл, Маршалл младший (ред.). Комбинаторный анализ . Труды симпозиумов по прикладной математике. Том 10. Провиденс, Род-Айленд: Американское математическое общество. стр. 175–178. MR 0114323 .

[7] Мун, Дж.В.; Мозер, Л. (1966). «Экстремальная задача теории матриц» . Математический весник . 3(18) (37): 209–211. МР 0207570 .

[8] Карлсон, Джордан; Столарски, Дэниел (октябрь 2004 г.). «Правильное решение игры Берлекэмпа с переключением» . Дискретная математика . 287 (1–3): 145–150. дои : 10.1016/j.disc.2004.06.015 . МР 2094708 .

[9] Слоан, Нью-Джерси (ред.). «Последовательность A005311 (Решение игры Берлекампа с переключением (или игры с лампочкой) на доске n X n)» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.

[10] Пеллегрино, Д.; Рапосо-младший, А. (2022). «Константы неравенства Кахане – Салема – Зигмунда, асимптотически ограниченные единицей». Журнал функционального анализа . 282 (2): 109293. arXiv : 2006.12892 . дои : 10.1016/j.jfa.2021.109293 . S2CID 231895733 .

[11] Пеллегрино, Д.; Рапосо-младший, А. (2021). «Верхние оценки констант неравенства Беннета и игры с переключением Гейла-Берлекэмпа». arXiv : 2111.00445v3 [ math.CO ].

[komsul-12] Jump up to: Перейти обратно: ^а ^б Комлос, Дж . ; Сулёк, М. (1970). «О сумме элементов $\pm 1$ матрицы». Комбинаторная теория и ее приложения, II (Proc. Colloq., Balatonfüred, 1969) . С. 721–728. MR 0299500 .

[13] Бергер, Бонни (1997). «Метод четвертого момента». SIAM Journal по вычислительной технике . 26 (4): 1188–1207. дои : 10.1137/S0097539792240005 . МР 1460721 . S2CID 14313557 .

[14] Рот, Рон М.; Вишванатан, Кришнамурти (2008). «О сложности декодирования кода Гейла – Берлекэмпа». Транзакции IEEE по теории информации . 54 (3): 1050–1060. дои : 10.1109/TIT.2007.915716 . МР 2445050 .

[15] Карпински, Марек ; Шуди, Уоррен (2009). «Схемы аппроксимации линейного времени для игры Гейла – Берлекампа и связанные с ней задачи минимизации». В Митценмахере, Майкл (ред.). Материалы 41-го ежегодного симпозиума ACM по теории вычислений, STOC 2009, Бетесда, Мэриленд, США, 31 мая — 2 июня 2009 г. АКМ. стр. 313–322. arXiv : 0811.3244 . дои : 10.1145/1536414.1536458 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]