Сильвер - математическая игра для двух игроков, изобретенная Джоном Х. Конвеем . Это обсуждается в главе 18 книги « Лучшие способы математической игры» . Эта статья резюмирует эту главу.
Два игрока по очереди называют положительные целые числа больше 1, которые не являются суммой неотрицательных кратных ранее названных целых чисел. Игрок, который не может назвать такое число, проигрывает. Например, если игрок A открывает 2, B может выиграть, назвав 3.
Монета Сильвера названа в честь Джеймса Джозефа Сильвестра , который доказал, что если a и b являются относительно простыми положительными целыми числами, то ( a - 1) ( b - 1) - 1 является наибольшим числом, которое не является суммой неотрицательных кратных a и б . Таким образом, если a и b - первые два хода в игре с серебряной монетой, эта формула дает наибольшее число, которое еще можно сыграть. В более общем смысле, если наибольший общий делитель ходов, сыгранных до сих пор, равен g , тогда может остаться только конечное число, кратное g , и после того, как все они сыграны, g должен уменьшиться на следующем ходу. Следовательно, каждая игра с серебряной монетой должна в конце концов закончиться. Когда в игре с серебряной монетой остается только конечное число оставшихся ходов, наибольшее число, которое еще можно сыграть, называется числом Фробениуса , а нахождение этого числа называется проблемой с монетами .
Пример
Пример игры между A и B:
- A открывается с 5. Теперь ни один из игроков не может назвать 5, 10, 15, ....
- B имена 4. Теперь ни один игрок не может назвать 4, 5, 8, 9, 10 или любое число больше 11.
- Имена 11. Теперь остались только цифры 2, 3, 6 и 7.
- B имена 6. Теперь остались только цифры 2, 3 и 7.
- Имена 7. Теперь остались только цифры 2 и 3.
- B имена 2. Теперь осталось только 3.
- A называет 3, ничего не оставляя B, и побеждает.
Каждый ход A приводил к выигрышной позиции.
Анализ
В отличие от многих аналогичных математических игр, система серебряных монет не решена полностью, главным образом потому, что многие позиции имеют бесконечно много возможных ходов. Кроме того, основная теорема, которая определяет класс выигрышных позиций, согласно Р.Л. Хатчингсу, гарантирует, что такая позиция имеет выигрышную стратегию, но не определяет стратегию. Теорема Хатчингса утверждает, что любое из простых чисел 5, 7, 11, 13,… выигрывает в качестве первого хода, но очень мало известно о последующих выигрышных ходах: это единственные известные выигрышные варианты.
Когда наибольший общий делитель ходов, которые были сделаны до сих пор, равен 1, оставшийся набор чисел, которые можно сыграть, будет конечным набором и может быть описан математически как набор пробелов числовой полугруппы . Некоторые из этих конечных позиций, включая все позиции после того, как второй игрок ответил на один из выигрышных ходов Хатчингса, допускают специальный ход, который Сичерман называет «эндер». Конец - это число, которое можно сыграть только сразу: игра любого другого числа исключит его. Если эндер существует, это всегда самое большое число, которое еще можно воспроизвести. Например, после ходов (4,5) наибольшее число, которое все еще можно сыграть, равно 11. Игра 11 не может исключать меньшие числа, но можно сыграть любое из меньших доступных чисел (1, 2, 3, 6 или 7) исключает игру 11, поэтому 11 - это конец. Когда существует конец, следующий игрок может выиграть, следуя аргументу о краже стратегии . Если один из незавершенных ходов может выиграть, следующий игрок делает этот выигрышный ход. И если ни один из ходов, не являющихся завершающими, выигрывает, то следующий игрок может выиграть, сыграв последний ход и заставив другого игрока сделать один из других невыигрышных ходов. Однако, хотя этот аргумент доказывает, что следующий игрок может выиграть, он не определяет выигрышную стратегию для игрока. Сыграв в качестве первого хода простое число, равное 5 или больше, первый игрок в игре с серебряной монетой всегда может выиграть, следуя этой (неконструктивной) стратегии завершения на следующем ходу.
Существуют ли какие-либо неосновные выигрышные начальные ходы в серебряных монетах?
Если есть другие выигрышные варианты, они должны быть 3- мя гладкими числами (числа вида 2 i 3 j для неотрицательных целых чисел i и j ). Ибо, если сыграно любое число n , которое не имеет этой формы и не является простым, то второй игрок может выиграть, выбрав большой простой множитель n . Первые несколько трех гладких чисел, 1, 2, 3, 4, 6, 8, 9 и 12, являются проигрышными открытиями, для которых известны полные стратегии, с помощью которых второй игрок может выиграть. По лемме Диксона (примененной к парам показателей ( i , j ) этих чисел) только конечное число 3-гладких чисел может быть выигрышным открытием, но неизвестно, является ли какое-либо из них. Конвей (2017) предложил приз в размере $ 1000 для определения того, кто победит в первом нерешенного случае, открывающий ходе 16, как часть набора задач призовых также включая проблему 99-миллиметровую Конвея , минимальное расстояние от множества Данцера и thrackle гипотеза .
Рекомендации
- Берлекамп, Элвин Р .; Конвей, Джон Х .; Гай, Ричард К. (1982). «18. Император и его деньги» (PDF) . Выигрышные способы для ваших математических пьес , Vol. II: Игры в частности . Академическая пресса. С. 575–606.
- Конвей, Джон Х. (2017). «Пять проблем на 1000 долларов (обновление 2017 г.)» (PDF) . Он-лайн энциклопедия целочисленных последовательностей . Проверено 12 февраля 2019 .
- Гай, Ричард К. (1976). «Двадцать вопросов по поводу серебряной чеканки Конвея». Проблемы исследования. Американский математический ежемесячник . 83 (8): 634–637. DOI : 10.2307 / 2319892 . JSTOR 2319892 . Руководство по ремонту 1538138 .
- Гай, Ричард К. (2004). Нерешенные проблемы теории чисел (3-е изд.). Springer-Verlag . C7. ISBN 978-0-387-20860-2. Zbl 1058.11001 .
- Майкл, Т.С. (2009). «6. От марок к серебряным монетам». Как охранять художественную галерею и другие математические приключения . JHU Press. стр. 169 -206. ISBN 9780801897047.
- Сичерман, Джордж (2002). "Теория и практика Sylver Coinage" (PDF) . Целые числа . 2 . G2.
- Сильвестр, Джеймс Дж. (1884). «Вопрос 7382». Математические вопросы. Образовательные времена . 41 : 21.