Вычитание квадрата (также называемое « возьми квадрат» ) - это математическая игра на вычитание для двух игроков . В нее играют два человека, между которыми лежит стопка монет (или других жетонов). Игроки по очереди удаляют монеты из стопки, всегда удаляя ненулевое квадратное количество монет. Игра обычно ведется как обычная игра, что означает, что игрок, убравший последнюю монету, выигрывает. [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 является "горячим", если хотя бы одно "холодное" число может быть получено вычитанием положительного квадрата
Используя этот алгоритм, легко получить список холодных номеров:
Более быстрый алгоритм «разделяй и властвуй» может вычислять одну и ту же последовательность чисел с точностью до любого порога., во время . [4]
Холодных чисел бесконечно много. Более того, количество холодных чисел до некоторого порога должен быть как минимум пропорционален квадратному корню из , иначе их не хватило бы, чтобы обеспечить выигрышные ходы по всем горячим номерам. [3] Холодные числа, как правило, заканчиваются на 0, 2, 4, 5, 7 или 9. Холодные значения, заканчивающиеся другими цифрами, встречаются довольно редко. [3] Это особенно верно для холодных чисел, оканчивающихся на 6. Из всех более 180 000 холодных чисел менее 40 миллионов только одно оканчивается на 6: 11 356. [5]
Никакие два холодных числа не могут отличаться на квадрат, потому что если бы они были, то переход от большего из двух к меньшему было бы выигрышным, что противоречит предположению, что они оба холодные. Следовательно, по теореме Фюрстенберг-Саркози , то естественно , плотность холодных чисел равна нулю. То есть на каждый, и для всех достаточно больших , доля чисел до что холодно меньше чем . Сильнее, за каждое Существуют
холодные номера до . [6] Точная скорость роста холодных чисел остается неизвестной, но экспериментально количество холодных позиций до любого заданного порога кажется примерно . [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, ...
Мизерская игра
Вычитание квадрата можно также вести как игру с мизером , в которой игрок, совершивший последнее вычитание, проигрывает. Рекурсивный алгоритм определения «горячих» и «холодных» чисел для игры «Мизер» такой же, как и для обычной игры, за исключением того, что для игры «Мизер» число 1 является «холодным», а 2 - «горячим». Отсюда следует, что холодные числа для варианта Мизера - это холодные числа для нормальной игры, сдвинутые на 1:
Мизер разыгрывает «холодные» числа:1, 3, 6, 8, 11, 13, 16, 18, 21, 23, 35, 40, 45, ...
Смотрите также
Рекомендации
- ↑ Сильверман, Дэвид Л. (1971), «61. Вычесть квадрат», « Ваш ход: логические, математические и словесные головоломки для энтузиастов» , Dover Publications, p. 143, ISBN 9780486267319
- ^ Данн, Анджела (1980), «Вычесть квадрат», « Математические перегородки» , Dover Publications, стр. 102, ISBN 9780486239613
- ^ а б в г Голомб, Solomon W. (1966), "Математическое исследование игр " на вынос " ", Журнал комбинаторной теории , 1 : 443-458, DOI : 10.1016 / S0021-9800 (66) 80016-9 , MR 0209015.
- ^ а б Эппштейн, Дэвид (2018), «Более быстрая оценка игр на вычитание», Ито, Хиро; Леонарди, Стефано; Пагли, Линда ; Пренсипи, Джузеппе (ред.), Proc. 9-я Международная конференция по развлечениям с алгоритмами (FUN 2018) , Leibniz International Proceedings in Informatics (LIPIcs), 100 , Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, стр. 20: 1–20: 12, doi : 10.4230 / lipics.fun.2018.20
- ^ Буш, Дэвид (12 октября 1992 г.), "Уникальность 11 356" , sci.math
- ^ Пинц, Янош ; Steiger, WL; Семереди, Эндре (1988), «О множествах натуральных чисел, разностное множество которых не содержит квадратов», Журнал Лондонского математического общества , вторая серия, 37 (2): 219–231, doi : 10.1112 / jlms / s2-37.2. 219 , Руководство по ремонту 0928519.