Олимпиадная задача по теории чисел, инвариантам и алгоритмам для 8–10 классов
Задача
Двое играющих по очереди пишут – каждый на своей половине доски – по одному натуральному числу (повторения разрешаются) так, чтобы сумма всех чисел на доске не превосходила 10000. После того, как сумма всех чисел на доске становится равной 10000, игра заканчивается подсчетом суммы всех цифр на каждой половине. Выигрывает тот, на чьей половине сумма цифр меньше (при равных суммах – ничья). Может ли кто-нибудь из игроков выиграть, как бы ни играл противник?
Решение
Второй может гарантировать себе ничью: ему достаточно всё время писать числа с суммой цифр 1 (например, просто число 1) – действительно, он делает не больше ходов, чем первый, и на каждом ходе пишет число с не большей суммой цифр. Более того, по той же причине первый игрок проиграет, если хотя бы один раз напишет число с суммой цифр больше 1.
Пусть теперь оба игрока пишут только числа с суммой цифр 1 – то есть 1, 10, 100, 1000 или 10000. Тогда проиграть второй не может, а чтобы выиграть, ему нужно вынудить противника сделать больше ходов; или, что то же самое, сделать последний ход.
Докажем, что отвечая на числа 10 и 1000 числом 1, а на числа 100 и 1 числом 10, второй игрок добьётся успеха. Действительно, после каждого его хода сумма чисел на доске делится на 11, а 10000 на 11 не делится. Поэтому остаётся лишь проверить, что такой ход всегда легален – то есть что после него сумма не станет больше 10000. Для этого заметим, что первое большее 10000 число, кратное 11, – это 10010, а его нельзя получить, прибавляя 1 или 10 к числу, меньшему 10000.
Ответ
Второй игрок может выиграть.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь