Олимпиада имени Леонарда Эйлера 2020-2021 учебный год, III тур дистанционного этапа

Таня и Маша по очереди выписывают на доску натуральные числа, не превосходящие 1000, причем число 13 выписывать нельзя. Начинает Таня. Проигрывает та девочка, после хода которой на доске впервые появятся два одинаковых числа или два числа, отличающиеся на 17. Кто из девочек выиграет при правильной игре, и как ей для этого надо играть? ( И. Рубанов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Таня и Маша по очереди выписывают на доску натуральные числа, не превосходящие 1000, причем число 13 выписывать нельзя. Начинает Таня. Проигрывает та девочка, после хода которой на доске впервые появятся два одинаковых числа или два числа, отличающиеся на 17. Кто из девочек выиграет при правильной игре, и как ей для этого надо играть? (И. Рубанов)
Ответ. Таня.
Решение. Разобьём все числа от 1 до 1000 на 17 арифметических прогрессий с разностью 17 (будем называть их полями): 1, 18, 35, $\ldots$, 987; 2, 19, 36, $\ldots$, 988; $\ldots$; 12, 29, 46, $\ldots$, 998; 30, 47, $\ldots$, 999; 14, 31, 48, $\ldots$, 1000; 15, 32, 49, $\ldots$, 984; $\ldots$; 17, 34, 51, $\ldots$, 986. Так как $1000 = 17\cdot 58+14,$ каждое из первых 12 полей и 14-е поле будут иметь длину 59 (назовем эти поля длинными), а каждое из остальных четырех (в том числе то, где отсутствует запрещенное число 13) — длину 58 (назовем эти поля короткими). Отметим, что запрет выписывать число, отличающееся на 17 от уже выписанного, теперь можно описать как запрет выписывать число, соседнее в своем поле с уже выписанным.
   Пусть Таня предварительно разобьет все короткие поля на две пары и все длинные поля, кроме первого, на 6 пар. Первым ходом Таня выпишет на доску среднее число первого длинного поля: $1+17\cdot 29,$ а дальше играет так. Если Маша выписала на доску число $a = 1+17k$ из первого длинного поля, Таня выписывает число $1+17\cdot (58-k)$ из того же поля. Если же Маша выписала $m$-ое по счету число из любого другого поля, Таня выписывает $m$-ое число из парного поля.
   Заметим, что при такой игре Тани после каждого ее хода в каждом поле, кроме первого длинного, будут выписаны те же по счету числа, что и в парном ему поле. В первом же длинном поле после каждого хода Тани набор из всех использованных чисел будет симметричен относительно среднего числа. Поэтому если Маша смогла сделать свой очередной ход, не нарушив правил, то и Таня сможет, не нарушая правил, сделать ответный ход. Следовательно, Таня не может проиграть, а так как не позднее 999-го хода игра закончится, то проиграет Маша.