ВсОШ 2023, 11 класс, задача 5
( баллов) Изначально на доске написано единиц. Гриша и Глеб играют в игру, делая ходы по очереди. Своим ходом Гриша возводит некоторые чисел на доске в квадрат. Глеб своим ходом выбирает несколько (возможно, ни одного) чисел на доске и увеличивает каждое из них на . Если в течение ходов на доске появится число, делящееся на , то побеждает Глеб, иначе побеждает Гриша. Кто из игроков имеет выигрышную стратегию, если первым ходит Гриша? (Г. Никитин)
Ответ. Побеждает Гриша.
Решение. Заметим, что . Гриша разобьёт числа на доске на две группы по и будет возводить в квадрат числа из первой группы и из второй группы по очереди. Легко видеть, что квадраты целых чисел, не кратных , при делении на могут давать лишь остатки , и . Следовательно, после увеличения максимум на числа на доске будут давать при делении на только остатки , , , , и . Значит, ни одно из чисел не будет делиться , а поэтому не будет делиться и на .
Замечание. Существуют и другие решения.