Вычесть квадрат

«Вычитание квадрата» (также называемое « возьми квадрат для двух игроков ») — это математическая игра на вычитание . В нее играют два человека, между которыми лежит стопка монет (или других жетонов). Игроки по очереди вынимают монеты из стопки, всегда удаляя ненулевое квадратное количество монет. В игру обычно играют как в обычную игру, а это означает, что побеждает игрок, который уберет последнюю монету. ^[1]^[2] Это беспристрастная игра , то есть набор ходов, доступных из любой позиции, не зависит от того, чей ход. Соломон В. Голомб приписывает изобретение этой игры Ричарду А. Эпштейну . ^[3]

Пример

Обычная игра, начинающаяся с 13 монет, является победой для первого игрока при условии, что он начинает с вычитанием 1:

player 1: 13 - 1*1 = 12

У игрока 2 теперь есть три варианта выбора: вычесть 1, 4 или 9. В каждом из этих случаев игрок 1 может гарантировать, что в течение нескольких ходов число 2 будет передано игроку 2:

player 2: 12 - 1*1 = 11        player 2:       12 - 2*2 = 8               player 2: 12 - 3*3 = 3
player 1: 11 - 3*3 =  2        player 1:        8 - 1*1 = 7               player 1:  3 - 1*1 = 2
                               player 2:  7 - 1*1 = 6 or: 7 - 2*2 = 3   
                               player 1:  6 - 2*2 = 2     3 - 1*1 = 2

Теперь игрок 2 должен вычесть 1, а игрок 1 впоследствии делает то же самое:

player 2:  2 - 1*1 = 1
player 1:  1 - 1*1 = 0
  player 2 loses

Математическая теория

В приведенном выше примере число «13» представляет выигрышную или «горячую» позицию, а число «2» представляет собой проигрышную или «холодную» позицию. Учитывая список целых чисел, каждое из которых помечено как «горячее» или «холодное», стратегия игры проста: попробуйте передать «холодное» число своему противнику. Это всегда возможно, если вам предъявят «горячий» номер. Какие числа являются «горячими», а какие «холодными», можно определить рекурсивно :

цифра 0 — «холодная», а 1 — «горячая».
если все числа 1 .. N классифицированы как «горячие» или «холодные», то
- число N+1 является «холодным», если вычитанием положительного квадрата можно получить только «горячие» числа.
- число N+1 является «горячим», если хотя бы одно «холодное» число можно получить вычитанием положительного квадрата

Используя этот алгоритм, легко получить список холодных номеров:

0, 2, 5, 7, 10, 12, 15, 17, 20, 22, 34, 39, 44, … (последовательность A030193 в OEIS )

Более быстрый алгоритм «разделяй и властвуй» может вычислить одну и ту же последовательность чисел с точностью до любого порога. $n$ , во времени $O(n\log ^{2}n)$ . ^[4]

Холодных чисел бесконечно много. Более сильно количество холодных чисел до некоторого порога $n$ должно быть как минимум пропорционально квадратному корню из $n$ , иначе их не хватило бы, чтобы обеспечить выигрышные ходы со всех горячих номеров. ^[3] Холодные числа, как правило, заканчиваются на 0, 2, 4, 5, 7 или 9. Холодные значения, оканчивающиеся другими цифрами, встречаются довольно редко. ^[3] Это особенно справедливо для холодных чисел, оканчивающихся на 6. Из всех более чем 180 000 холодных чисел менее 40 миллионов только одно оканчивается на 6: 11 356. ^[5]

Никакие два холодных числа не могут отличаться на квадрат, потому что если бы они различались, то ход от большего из двух к меньшему был бы выигрышным, что противоречит предположению, что они оба холодные. Следовательно, по теореме Фюрстенберга–Саркози естественная плотность холодных чисел равна нулю. То есть для каждого $\epsilon >0$ , и для всех достаточно больших $n$ , дробь чисел до $n$ которые холодны, меньше, чем $\epsilon$ . Сильнее, для каждого $n$ есть

O(n/(\log n)^{{\frac {1}{4}}\log \log \log \log n})

холодные числа до $n$ . ^[6] Точная скорость роста холодных чисел остается неизвестной, но экспериментально количество холодных позиций до любого заданного порога $n$ кажется, примерно $n^{0.7}$ . ^[4]

Расширения

В игру «Вычитание квадрата» также можно играть с несколькими числами. На каждом ходу игрок для совершения хода сначала выбирает одно из чисел, а затем вычитает из него квадрат. Такую «сумму нормальных игр» можно проанализировать с помощью теоремы Спрага – Гранди . Эта теорема утверждает, что каждая позиция в игре «Вычитание квадрата» может быть отображена на эквивалентный размер кучи нимов . Оптимальная игра состоит в переходе к набору чисел, в котором ним -сумма их эквивалентных размеров кучи нимов равна нулю, если это возможно. Эквивалентный размер кучи нимов позиции может быть рассчитан как минимальное исключенное значение эквивалентных размеров позиций, которые могут быть достигнуты за один ход. Для позиций вычитания в квадрате значений 0, 1, 2,... эквивалентные размеры кучи nim равны

0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 3, 2, 3, 4, … (последовательность A014586 в OEIS ).

В частности, позиция вычитания квадрата является холодной тогда и только тогда, когда ее эквивалентный размер кучи nim равен нулю.

Также можно играть в варианты этой игры, используя другие разрешенные ходы, кроме квадратных чисел. Например, Голомб определил аналогичную игру, основанную на последовательности Мозера-де Брюйна , последовательности, которая растет с той же асимптотической скоростью , что и квадраты, для которой можно легче определить набор холодных позиций и определить легко вычислимую оптимальная стратегия хода. ^[3]

Игрокам также могут быть добавлены дополнительные цели без изменения условий выигрыша. Например, победителю может быть присвоен «счет» в зависимости от того, сколько ходов ему потребовалось для победы (цель состоит в том, чтобы получить наименьший возможный результат), а проигравшему может быть дана цель заставить победителя потратить как можно больше времени, чтобы достичь победа. С учетом этой дополнительной пары голов и предположения об оптимальной игре обоих игроков очки для стартовых позиций 0, 1, 2, ... равны

0, 1, 2, 3, 1, 2, 3, 4, 5, 1, 4, 3, 6, 7, 3, 4, 1, 8, 3, 5, 6, 3, 8, 5, 5, 1, 5, 3, 7, … (последовательность A338027 в OEIS ).

игра страдания

В «Вычитание квадрата» также можно играть как в мизерную игру, в которой игрок, сделавший последнее вычитание, проигрывает. Рекурсивный алгоритм определения «горячих» и «холодных» чисел для игры «мизер» такой же, как и для обычной игры, за исключением того, что для игры «мизер» число 1 является «холодным», а число 2 — «горячим». Отсюда следует, что холодные числа для варианта Misère — это холодные числа для обычной игры, смещенные на 1:

Misère play 'cold' numbers:
1, 3, 6, 8, 11, 13, 16, 18, 21, 23, 35, 40, 45, ...

См. также

Ссылки

^ Сильверман, Дэвид Л. (1971), «61. Вычитание квадрата», Ваш ход: логика, математика и словесные головоломки для энтузиастов , Dover Publications, стр. 143, ISBN 9780486267319
^ Данн, Анджела (1980), «Вычитание квадрата», Mathematical Bafflers , Dover Publications, стр. 102, ISBN 9780486239613
^ Jump up to: ^а ^б ^с ^д Голомб, Соломон В. (1966), «Математическое исследование игр на вынос» , Журнал комбинаторной теории , 1 (4): 443–458, doi : 10.1016/S0021-9800(66)80016-9 , МР 0209015 .
^ Jump up to: ^а ^б Эппштейн, Дэвид (2018), «Быстрая оценка игр на вычитание», Ито, Хиро; Леонарди, Стефано; Пагли, Линда ; Пренсипи, Джузеппе (ред.), Proc. 9-я Международная конференция по развлечениям с алгоритмами (FUN 2018) , Международные труды Лейбница по информатике (LIPIcs), том. 100, Дагштуль, Германия: Замок Дагштуль - Центр компьютерных наук Лейбница, стр. 20: 1–20: 12, doi : 10.4230/lipics.fun.2018.20 , ISBN 9783959770675 , S2CID 4952124
^ Буш, Дэвид (12 октября 1992 г.), «Уникальность 11 356» , sci.math.
^ Пинц, Янош ; Штайгер, В.Л.; Семереди, Эндре (1988), «О множествах натуральных чисел, разностное множество которых не содержит квадратов», Журнал Лондонского математического общества , вторая серия, 37 (2): 219–231, doi : 10.1112/jlms/s2-37.2. 219 , МР 0928519 .

[1] Сильверман, Дэвид Л. (1971), «61. Вычитание квадрата», Ваш ход: логика, математика и словесные головоломки для энтузиастов , Dover Publications, стр. 143, ISBN 9780486267319

[2] Данн, Анджела (1980), «Вычитание квадрата», Mathematical Bafflers , Dover Publications, стр. 102, ISBN 9780486239613

[golomb-3] Jump up to: ^а ^б ^с ^д Голомб, Соломон В. (1966), «Математическое исследование игр на вынос» , Журнал комбинаторной теории , 1 (4): 443–458, doi : 10.1016/S0021-9800(66)80016-9 , МР 0209015 .

[fesg-4] Jump up to: ^а ^б Эппштейн, Дэвид (2018), «Быстрая оценка игр на вычитание», Ито, Хиро; Леонарди, Стефано; Пагли, Линда ; Пренсипи, Джузеппе (ред.), Proc. 9-я Международная конференция по развлечениям с алгоритмами (FUN 2018) , Международные труды Лейбница по информатике (LIPIcs), том. 100, Дагштуль, Германия: Замок Дагштуль - Центр компьютерных наук Лейбница, стр. 20: 1–20: 12, doi : 10.4230/lipics.fun.2018.20 , ISBN 9783959770675 , S2CID 4952124

[5] Буш, Дэвид (12 октября 1992 г.), «Уникальность 11 356» , sci.math.

[6] Пинц, Янош ; Штайгер, В.Л.; Семереди, Эндре (1988), «О множествах натуральных чисел, разностное множество которых не содержит квадратов», Журнал Лондонского математического общества , вторая серия, 37 (2): 219–231, doi : 10.1112/jlms/s2-37.2. 219 , МР 0928519 .

[1]

[2]

[3]

[4]

[5]

[6]