ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 111910
Темы:    [ Теория игр (прочее) ]
[ Инварианты ]
[ Делимость чисел. Общие свойства ]
Сложность: 4+
Классы: 8,9,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.


Ответ

Второй игрок может выиграть.

Замечания

Можно показать, что если заменить 10000 в условии на произвольное число N, то второй игрок может выиграть тогда и только тогда, когда N даёт нечётный остаток при делении на 11.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 72
Год 2009
Класс
Класс 8
задача
Номер 6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .