Введение

Сильвер - математическая игра для двух игроков, изобретённая Джоном Х. Конвеем. Два игрока по очереди называют положительные целые числа, которые не являются суммой неотрицательных кратных ранее названных чисел. Игрок, назвавший 1, проигрывает. Например, если игрок А начинает с 2, игрок B может выиграть, назвав 3, так как игрок А будет вынужден назвать 1. Игра Сильвера является примером игры с мизерным условием окончания, поскольку проигрывает игрок, который сделал последний ход. Игра Сильвера названа в честь Джеймса Джозефа Сильвестра, который доказал, что если a и b – взаимно простые положительные целые числа, то (a − 1)(b − 1) − 1 является наибольшим числом, которое нельзя представить в виде суммы неотрицательных кратных a и b. Таким образом, если a и b – первые два хода в игре Сильвера, эта формула даёт наибольшее число, которое ещё можно назвать. В более общем случае, если наибольший общий делитель всех сделанных ходов равен g, то остаётся лишь конечное число кратных g, которые можно назвать, и после того, как все они названы, g должно уменьшиться следующим ходом. Следовательно, любая игра Сильвера должна в конечном итоге завершиться. Когда в игре Сильвера остаётся лишь конечное число возможных ходов, наибольшее из этих чисел называется числом Фробениуса, а задача нахождения этого числа – проблемой монет.

Анализ

В отличие от многих аналогичных математических игр, игра в сильвер-коины (или серебряные монеты) не была полностью решена, главным образом потому, что многие позиции имеют бесконечно много возможных ходов. Кроме того, основная теорема, определяющая класс выигрышных позиций, благодаря Р. Л. Хатчингу, гарантирует, что такая позиция имеет выигрышную стратегию, но не указывает саму стратегию. Теорема Хатчинга утверждает, что любое из простых чисел 5, 7, 11, 13, выигрывает первым ходом, но о последующих выигрышных ходах известно очень мало: это единственные известные выигрышные дебюты. Когда наибольший общий делитель сделанных ходов равен 1, оставшийся набор чисел, которые можно сыграть, будет конечным и может быть математически описан как множество пропусков числовой полугруппы. Некоторые из этих конечных позиций, включая все позиции после того, как второй игрок ответил на один из выигрышных ходов Хатчинга, допускают специальный ход, который Сихерман называет «эндером». Эндер – это число, которое можно сыграть только немедленно: игра любого другого числа исключает возможность его сыграть. Если эндер существует, то это всегда наибольшее число, которое ещё можно сыграть. Например, после ходов (4, 5) наибольшее число, которое ещё можно сыграть, – 11. Игра 11 не исключает никакие меньшие числа, но игра любого из меньших доступных чисел (1, 2, 3, 6 или 7) исключит возможность сыграть 11, поэтому 11 является эндером. Когда существует эндер, следующий игрок может выиграть, следуя аргументу «кражи стратегии». Если один из не-эндеровских ходов может выиграть, следующий игрок делает этот выигрышный ход. И если ни один из не-эндеров не выигрывает, то следующий игрок может выиграть, сыграв эндер и вынудив другого игрока сделать один из остальных невыигрышных ходов. Однако, хотя этот аргумент доказывает, что следующий игрок может выиграть, он не определяет выигрышную стратегию для игрока. После того, как первым ходом сыграно простое число, равное 5 или больше, первый игрок в игре в сильвер-коины всегда может выиграть, следуя этой (неконструктивной) эндер-стратегии своим следующим ходом. Если существуют другие выигрышные дебюты, то они должны быть 3-гладкими числами (числами вида 2<sup>i</sup>3<sup>j</sup>, где i и j – неотрицательные целые числа). Если сыграно любое число n, которое не имеет такой формы и не является простым, то второй игрок может выиграть, выбрав большой простой делитель n. Первые 3-гладкие числа 1, 2, 3, 4, 6, 8, 9 и 12 – все проигрышные дебюты, для которых известны полные стратегии, позволяющие второму игроку выиграть. По лемме Диксона (применяемой к парам показателей (i, j) этих чисел), лишь конечное число 3-гладких чисел может быть выигрышными дебютами, но неизвестно, существует ли хотя бы одно такое число. В 2017 году был предложен приз в размере 1000 долларов за определение победителя в первом нерешенном случае, дебюте 16, в рамках набора призовых задач, включающего также проблему графа Конвея с 99 вершинами, задачу о минимальном расстоянии между множествами Данцера и гипотезу Трэкла.