Вычесть квадрат - Subtract a square

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

пример

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

игрок 1: 13 - 1 * 1 = 12

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

игрок 2: 12 - 1 * 1 = 11 игрок 2: 12 - 2 * 2 = 8 игрок 2: 12 - 3 * 3 = 3 игрок 1: 11 - 3 * 3 = 2 игрока 1: 8 - 1 * 1 = 7 игроков 1: 3 - 1 * 1 = 2 игрока 2: 7 - 1 * 1 = 6 или: 7 - 2 * 2 = 3 игрока 1: 6 - 2 * 2 = 2 3 - 1 * 1 = 2

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

игрок 2: 2 - 1 * 1 = 1 игрок 1: 1 - 1 * 1 = 0 игрок 2 проигрывает

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

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

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

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

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

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

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

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

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

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

Расширения

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

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 ).

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

Также можно играть в варианты этой игры, используя другие разрешенные ходы, кроме квадратных чисел. Например, Голомб определил аналогичную игру, основанную на Последовательность Мозера – де Брейна, последовательность, которая растет на аналогичной асимптотическая скорость квадратам, для которых можно более легко определить набор холодных позиций и определить легко вычисляемую оптимальную стратегию хода.^[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 ).

Мизерская игра

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

Мизер разыгрывает «холодные» числа: 1, 3, 6, 8, 11, 13, 16, 18, 21, 23, 35, 40, 45, ...

Смотрите также

использованная литература

^ Сильверман, Дэвид Л. (1971), «61. Вычесть квадрат», Ваш ход: логические, математические и словесные головоломки для энтузиастов, Dover Publications, стр. 143, ISBN 9780486267319
^ Данн, Анджела (1980), «Вычесть квадрат», Математические перегородки, Dover Publications, стр. 102, ISBN 9780486239613
^ ^а ^б ^c ^d Голомб, Соломон В. (1966), "Математическое исследование игр" на вынос"", Журнал комбинаторной теории, 1: 443–458, Дои:10.1016 / S0021-9800 (66) 80016-9, Г-Н 0209015.
^ ^а ^б Эппштейн, Дэвид (2018), «Более быстрая оценка игр на вычитание», Ито, Хиро; Леонарди, Стефано; Пагли, Линда; Пренсипи, Джузеппе (ред.), Proc. 9-я Международная конференция по развлечениям с алгоритмами (FUN 2018), Международный журнал Лейбница по информатике (LIPIcs), 100, Дагштуль, Германия: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, стр. 20: 1–20: 12, Дои:10.4230 / lipics.fun.2018.20
^ Буш, Дэвид (12 октября 1992 г.), «Уникальность 11 356», sci.math
^ Пинц, Янош; Steiger, W. L .; Семереди, Эндре (1988), «О множествах натуральных чисел, разностное множество которых не содержит квадратов», Журнал Лондонского математического общества, Вторая серия, 37 (2): 219–231, Дои:10.1112 / jlms / s2-37.2.219, Г-Н 0928519.

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

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

[golomb-3] а ^б ^c ^d Голомб, Соломон В. (1966), "Математическое исследование игр" на вынос"", Журнал комбинаторной теории, 1: 443–458, Дои:10.1016 / S0021-9800 (66) 80016-9, Г-Н 0209015.

[fesg-4] а ^б Эппштейн, Дэвид (2018), «Более быстрая оценка игр на вычитание», Ито, Хиро; Леонарди, Стефано; Пагли, Линда; Пренсипи, Джузеппе (ред.), Proc. 9-я Международная конференция по развлечениям с алгоритмами (FUN 2018), Международный журнал Лейбница по информатике (LIPIcs), 100, Дагштуль, Германия: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, стр. 20: 1–20: 12, Дои:10.4230 / lipics.fun.2018.20

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

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

[1]

[2]

[3]

[4]

[5]

[6]