Решение задачи 474

Условие:

На доске записано число 111...111 (всего 99 единиц). Вика и Наташа играют в следующую игру, делая ходы по очереди. Начинает Вика. За ход игрок либо записывает ноль вместо одной из единиц, кроме первой и последней, либо стирает один из нулей. Проигрывает тот, после чьего хода на доске в первый раз появится число, делящееся на 11. Кто выигрывает при правильной игре?

Решение:

Покажем, как должна играть Вика, чтобы выиграть. Первым ходом Вика может сделать число 101....1 (97 единиц после нуля). Наташа своим первым ходом может либо стереть ноль, тогда получится число 1...1 (98 единиц), либо поменять какую-ту единицу на ноль, тогда получится число 101...101....1. В обоих случаях Вика своим вторым ходом может сделать число 101...1 (96 единиц после нуля). Продолжая по аналогии, получаем, что Вика после своего k-го хода может делать число 101....1 (98−k единиц после нуля).

Покажем, что число 101...1 никогда не делится на 11. Легко проверяется, что число 101 и 1011 не делятся на 11. Возьмем число 101 и будет постепенно дописывать по две единицы справа. Тогда полученные числа не будут делиться на 11, так как в сумму цифр, стоящих на четных разрядах, добавляется единица, и в сумму цифр, стоящих на нечетных разрядах, добавляется единица (пользуемся признаком делимости на 11). Аналогично с числами, получаемыми из 1011. Значит, Вика после своих ходов не проигрывает.

Получается, после своего 97-го хода (Наташа может уже проиграет к этому моменту) Вика сделает число 101, на что Наташа ответит числом 11 и проиграет.

Ответ: Вика.