Задание №178309: Турнир Ломоносова 2012

2. «Чеканка монет».
а) Второй может отчеканить вторую из упомянутых в условии монет.
Очевидно, первому тогда останется только чеканить 1 золотой.

б) Нет. Второй может отчеканить 6 золотых и выиграть. В самом
деле, первый после такого хода может выпустить монету 2 золотых,
а также любого нечётного номинала. Выпускать 1 никому не выгодно,
2 и 3 тоже (см. п. «а»).
Остальные монеты можно разбить на пары: (5; 7), (9; 11), (13; 15) и
так далее. Теперь в какую пару ни пойдёт первый, второй ходит в неё
же. При этом из множества допустимых ходов исключается эта пара и
все бо´льшие. Далее этот приём нужно повторить несколько раз.
в) Нет. Нужно отчеканить 4 золотых и далее действовать как в
предыдущем пункте.
г) После указанных ходов первый может отчеканить 19 золотых.
Тогда у второго останутся такие возможности: 1, 2, 3, 4, 7, 8, 9, 13, 14.
Первые три хода бессмысленны, а остальные можно разбить на пары
(4; 7), (8; 9), (13; 14) и действовать так же, как в пункте «б».
д) Случаи k < 4 разбираются непосредственно.

24

Если k (cid:62) 4, то покажем, что максимальное непредставимое число
есть 4k 5. В самом деле, если 5a + kb = 4k 5, то 5(a + 1) = k(4 b).
Посколь − ку НОД(k;5) = 1, то (4 b) кратно 5, − при этом b (cid:62) 0 и 4 b − > 0.
− −
Эти условия несовместимы.
Покажем теперь, как набрать любое число золотых, большее 4k 5,
−
монетами по 5 и k золотых.
Понятно, что достаточно показать это лишь для первых пяти чисел
после 4k 5. Число k при делении на 5 может давать остатки от 1 до 4.
−
Нетрудно проверить, что в каждом из четырёх случаев числа k, 2k, 3k
и 4k при делении на 5 будут давать все остатки от 1 до 4 в каком-то
порядке. Это значит, что при любом i от 1 до 4 одно из чисел (k i),
(2k i), (3k i) или (4k i) будет делиться на 5 (заметим, что k
−(cid:62)
4,
− − −
то есть все эти числа неотрицательны). То есть, при всяком i мы смо
жем одну из этих сумм набрать монетами по 5 золотых, а потом, если
нужно, добавить несколько монет по k золотых, чтобы получилось
ровно (4k i). Таким образом мы набираем суммы (4k 4), (4k 3),
− − −
(4k 2) и (4k 1). Сумма же 4k набирается очевидным способом.
− −
е) Воспользуемся указанием. Если первый казначей, отчеканив мо
нету (4k 5), проиграет после того, как второй отчеканит монету m,
−
ему следует применить стратегию соперника и сразу чеканить m. Из
вестно, что соперник выигрывает, если отчеканены монеты 5, k, (4k 5)
−
и m. Но, оказывается, сумма (4k 5) набирается монетами 5, k и m, так
−
что первый, сразу отчеканив m, попадает в выигрышное положение.
Осталось доказать только что сформулированное утверждение.
Для доказательства все целые числа от 0 до 5k разобьём на два
класса: «хорошие» вида 5a + kb, где a,b (cid:62) 0, и «плохие» (все остальные).
Найдём количество хороших чисел. Выпишем все числа вида 5a + kb,
где a,b (cid:62) 0, a (cid:54) k, b (cid:54) 5. Все эти числа хорошие и «почти все раз
личны»: именно, если 5x + ky = 5x + ky , то можно считать, что
1 1
5(x x ) = k(y y) (cid:62) 0, а тогда (y y) кратно 5. Если y = y, то
1 1 1 1
x = − x, то есть − числа совпадают, если − же нет, то y y (cid:62) 5, то есть
1 1
y (cid:62) 5, но тогда y = 5. −
1 1
Отсюда нетрудно получить, что y = 0, x = 0 и x = k. То есть,
1
среди указанных 6(k + 1) чисел совпадают только два: 5k + k 0 и
·
5 0 + k 5. Остальные же 6(k + 1) 2 числа различны и разбиваются
· · (cid:0) − (cid:1)
на пары 5a + kb; 5(k a) + k(5 b) , причём сумма чисел в каж
− −
дой паре равна 10k. Заметим, что ровно одно число в паре лежит
в нашем диапазоне (от 0 до 5k), то есть в этом диапазоне ровно
3(k + 1) 1 + 1 = 3(k + 1) хорошее число.
−
25

Как уже показано ранее, хороши числа от 4k 4 до 5k вклю
−
чительно, их ровно k + 5. Итак, в диапазоне от 0 до 4k 5 ровно
−
3(k + 1) k 5 = 2k 2 хороших чисел. Но всего там чисел 4k 4,
− − − −
то есть ровно половина из них хорошие. Все числа от 0 до 4k 5
−
разбиваются на пары, дающие в сумме 4k 5. Оба числа в паре не
−
могут быть хорошими, иначе (4k 5) было бы хорошим. Значит, в каж
−
дой паре есть по крайней мере одно плохое число. Но плохих чисел
столько же, сколько и пар, так что плохое число в паре ровно одно.
Поэтому, если число m плохое, то (4k 5 m) — хорошее, а тогда
− −
4k 5 = 5x + ky + m, что и требовалось.
−
Примечание. В изложенном выше решении пункта «в» мы дока
зали наличие выигрышной стратегии у первого игрока (что и требо
валось в задании), но саму эту выигрышную стратегию не построили.
Мы не выяснили, когда вторым своим ходом первому игроку нужно
чеканить монету (4k 5), а когда m, а также — как вычислить подхо
−
дящее m.
Число (4k 5) является последним, которое нельзя разменять моне
−
тами достоинством 5 и k (см. решение пункта «д»). Тем самым для
любого конкретного k игровую ситуацию можно полностью исследо
вать перебором конечного количества вариантов и, в частности, найти
подходящее число m. Но какой-либо достаточно простой формулы для
нахождения m(k) на момент написания данного текста неизвестно.
Также известно, что первый игрок выигрывает, если он начинает
игру не только с монеты достоинством 5, но и вообще с любого простого
числа, большего 3. Напротив, первый игрок проиграет, если начнёт игру
с числа, имеющего простой делитель, больший 3.
А, например, если первый игрок первым ходом отчеканит монету
достоинством 16, то про дальнейший ход игры (наличие выигрышной
стратегии у первого или у второго игрока) ничего не известно.