Серебряная чеканка

Чеканка серебряных монет — математическая игра для двух игроков, придуманная Джоном Х. Конвеем . ^[1] Два игрока по очереди называют положительные целые числа , которые не являются суммой неотрицательных кратных ранее названных целых чисел. Игрок, назвавший 1, проигрывает. Например, если игрок А открывает игру с 2, Б может выиграть, назвав 3, поскольку А вынужден назвать 1. ^[2] Чеканка серебряных монет — это пример игры, в которой используется мизерная игра, поскольку проигрывает игрок, который последним сможет двигаться.

Серебряная монета названа в честь Джеймс Джозеф Сильвестр , ^[2]^[3] который доказал, что если a и b являются относительно простыми положительными целыми числами, то ( a - 1)( b - 1) - 1 является наибольшим числом, которое не является суммой неотрицательных кратных a и b . ^[4] Таким образом, если a и b — первые два хода в игре с чеканкой серебряных монет, эта формула дает наибольшее число, которое еще можно сыграть. В более общем смысле, если наибольший общий делитель сыгранных на данный момент ходов равен g только конечное число кратных g , то осталось сыграть , и после того, как все они сыграны, g должно уменьшиться на следующем ходу. Следовательно, каждая игра в чеканку серебряных монет рано или поздно должна закончиться. ^[2] Когда в игре с серебряными монетами осталось только конечное число ходов, наибольшее число, которое еще можно сыграть, называется числом Фробениуса , а нахождение этого числа называется проблемой монеты . ^[5]

Пример

Пример игры между А и Б:

А открывается цифрой 5. Теперь ни один игрок не может назвать 5, 10, 15, ....
B называет 4. Теперь ни один игрок не может назвать 4, 5, 8, 9, 10 или любое число больше 11. (Пример: 27 = 4·3 + 5·3)
Имена 11. Теперь остались только числа 2, 3, 6 и 7.
Б называет 6. Теперь остались только числа 2, 3 и 7.
Имена 7. Теперь остались только цифры 2 и 3.
Б называет 2. Теперь осталось только число 3.
А называет 3, не оставляя ничего Б, и побеждает.

Каждый ход А приводил к выигрышной позиции.

Анализ

В отличие от многих подобных математических игр, чеканка серебряных монет не решена полностью, главным образом потому, что многие позиции имеют бесконечно много возможных ходов. Более того, основная теорема Р. Л. Хатчингса, определяющая класс выигрышных позиций, гарантирует, что такая позиция имеет выигрышную стратегию, но не идентифицирует стратегию. Теорема Хатчингса утверждает, что любое из простых чисел 5, 7, 11, 13,… выигрывает в качестве первого хода, но о последующих выигрышных ходах известно очень мало: это единственные известные выигрышные варианты. ^[2]^[5]

Когда наибольший общий делитель сделанных к настоящему моменту ходов равен 1, оставшийся набор чисел, которые можно разыграть, будет конечным набором и может быть описан математически как набор пробелов числовой полугруппы . Некоторые из этих конечных позиций, включая все позиции после того, как второй игрок ответил на один из выигрышных ходов Хатчингса, допускают специальный ход, который Зихерман называет «концом».Конец — это число, которое можно разыграть только немедленно: игра любого другого числа исключает это. Если существует конец, это всегда самое большое число, которое еще можно сыграть. Например, после ходов (4,5) наибольшее число, которое еще можно разыграть, равно 11. Игра 11 не может исключать любые меньшие числа, но игра любого из меньших доступных чисел (1, 2, 3, 6 или 7) исключает игру 11, поэтому 11 — это конец. Когда существует конец, следующий игрок может выиграть, следуя аргументу о краже стратегии . Если один из неконечных ходов может оказаться выигрышным, следующий игрок делает этот выигрышный ход. И если ни один из ходов без выигрыша не выиграет, то следующий игрок может выиграть, сыграв последний ход и заставив другого игрока сделать один из других невыигрышных ходов. Однако, хотя этот аргумент и доказывает, что следующий игрок может выиграть, он не определяет выигрышную стратегию для игрока. После того, как первым ходом было выбрано простое число 5 или больше, первый игрок в игре с серебряными монетами всегда может выиграть, следуя этой (неконструктивной) стратегии завершения на своем следующем ходу. ^[2]^[3]

Нерешенная задача по математике :

Есть ли в серебряных монетах какие-либо непростые выигрышные ходы?

(еще нерешенные задачи по математике)

Если есть еще какие-либо выигрышные дебюты, то они должны быть 3- гладкими числами (числа вида $2 я 3 дж$ для неотрицательных целых чисел $i$ и $j$ ).Ведь если разыгрывается любое число $n,$ которое не имеет этого вида и не является простым, то второй игрок может выиграть, выбрав большой простой делитель $n$ .Первые несколько 3-гладных чисел: 1, 2, 3, 4, 6, 8, 9 и 12 — все являются проигрышными дебютами, для которых известны полные стратегии, с помощью которых второй игрок может выиграть.По лемме Диксона (применённой к парам показателей $(i, j)$ этих чисел) только конечное число 3-гладких чисел может быть выигрышным дебютом, но неизвестно, являются ли какие-либо из них таковыми. ^[2]^[5] В 2017 году Конвей (2017) предложил приз в размере 1000 долларов за определение того, кто победит в первом нерешенном случае, первом ходе 16, как часть набора призовых задач, также включающих проблему Конвея с 99 графами , минимальное расстояние между множествами Данцера и гипотезу о трекле. . ^[6]

Ссылки

^ Гай, Ричард К. (1976). «Двадцать вопросов о серебряной чеканке Конвея». Проблемы исследования. Американский математический ежемесячник . 83 (8): 634–637. дои : 10.2307/2319892 . JSTOR 2319892 . МР 1538138 .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж Берлекамп, Элвин Р .; Конвей, Джон Х .; Гай, Ричард К. (1982). «18. Император и его деньги» (PDF) . Пути выигрыша в математических играх , Vol. II: Игры в частности . Академическая пресса. стр. 575–606.
^ Перейти обратно: ^а ^б Зихерман, Джордж (2002). «Теория и практика чеканки серебряных монет» (PDF) . Целые числа . 2 . Г2.
^ Сильвестр, Джеймс Дж. (1884). «Вопрос 7382». Математические вопросы. Образовательные времена . 41:21 .
^ Перейти обратно: ^а ^б ^с Гай, Ричард К. (2004). «С7. Проблема размена денег». Нерешенные проблемы теории чисел (3-е изд.). Спрингер-Верлаг . стр. 171–174. ISBN 978-0-387-20860-2 . Збл 1058.11001 .
^ Конвей, Джон Х. (2017). «Пять задач по 1000 долларов (обновление 2017 г.)» (PDF) . Электронная энциклопедия целочисленных последовательностей . Проверено 12 февраля 2019 г.

Дальнейшее чтение

Майкл, ТС (2009). «6. От марок до серебряных монет». Как охранять картинную галерею и другие дискретные математические приключения . Джу Пресс. стр. 169–206. ISBN 9780801897047 .

Внешние ссылки

Страница серебряных монет

[guy-1] Гай, Ричард К. (1976). «Двадцать вопросов о серебряной чеканке Конвея». Проблемы исследования. Американский математический ежемесячник . 83 (8): 634–637. дои : 10.2307/2319892 . JSTOR 2319892 . МР 1538138 .

[bcg-2] Перейти обратно: ^а ^б ^с ^д ^и ^ж Берлекамп, Элвин Р .; Конвей, Джон Х .; Гай, Ричард К. (1982). «18. Император и его деньги» (PDF) . Пути выигрыша в математических играх , Vol. II: Игры в частности . Академическая пресса. стр. 575–606.

[sicherman-3] Перейти обратно: ^а ^б Зихерман, Джордж (2002). «Теория и практика чеканки серебряных монет» (PDF) . Целые числа . 2 . Г2.

[sylvester-4] Сильвестр, Джеймс Дж. (1884). «Вопрос 7382». Математические вопросы. Образовательные времена . 41:21 .

[upint-5] Перейти обратно: ^а ^б ^с Гай, Ричард К. (2004). «С7. Проблема размена денег». Нерешенные проблемы теории чисел (3-е изд.). Спрингер-Верлаг . стр. 171–174. ISBN 978-0-387-20860-2 . Збл 1058.11001 .

[conway-6] Конвей, Джон Х. (2017). «Пять задач по 1000 долларов (обновление 2017 г.)» (PDF) . Электронная энциклопедия целочисленных последовательностей . Проверено 12 февраля 2019 г.

[1]

[2]

[3]

[4]

[5]

[6]