Всесиб 2025, отборочный этап, 10 класс, задача 5
( баллов) Пусть — произвольное натуральное число из интервала от до включительно. Два игрока, Вася и Петя играют на доске размера на в игру, выполняя по очереди следующие ходы. Сначала все клетки доски белые. Первым ходит Вася. За один свой ход Вася либо красит любую белую клетку в красный цвет, либо передаёт ход Пете. За один свой ход Петя либо красит в синий цвет любой квадрат доски размера на , состоящий целиком из белых клеток, либо передаёт ход Васе. Игра заканчивается, когда каждый из игроков одновременно отказывается от своего хода, в том числе, из-за невозможности его сделать. Если в итоге на доске окажется больше красных клеток, победит Вася, если больше синих — Петя, если поровну — ничья. Определите исход игры при каждом .
Ответ
Ответ. При игра оканчивается вничью, при всех остальных значениях выигрывает Вася.
Решение. Для произвольного разделим на с остатком: , . Разделим доску на квадратов размера на клеток, прямоугольников размера размера на клеток, прямоугольников размера на клеток, один квадрат размера на клеток и поставим в каждом из квадратов размера на точку в клетке со внутренними координатами . Прямоугольники и квадрат размера на при этом считаются расположенными вдоль верхней и правой сторон доски. Заметим, что на доске любой квадрат размера на клеток накрывает ровно одну клетку с точкой, поэтому своим ходом Петя всегда красит ровно одну клетку с точкой. Если их не остаётся, он не может сделать ход. Действительно, рассмотрим номера горизонталей и вертикалей, на пересечении которых находится произвольный квадрат размера на . В обоих случаях это будут последовательных натуральных чисел, ровно одно из которых даёт остаток , при делении на . Возьмём клетку, стоящую в соответствующих горизонтали и вертикали, она и будет иметь внутренние координаты в соответствующем квадрате разбиения. При этом внутренним координатам соответствует остаток .
Замечание. При другом выборе внутренних координат клетки с точкой, например , , . у нас может получиться таких клеток и рассуждения, приведённые дальше, уже не пройдут. Хотя утверждение о том, что на доске любой квадрат размера на клеток накрывает ровно одну клетку с точкой останется верным, часть из них Пете накрыть уже не удастся, и пропадёт точная оценка максимума числа ходов, которое могут сделать игроки. Тогда нельзя будет построить стратегию для Васи.
Стратегия Васи: он красит последовательно все ещё не окрашенные к моменту его очередного хода клетки с точками. Тогда каждый из них своим ходом красит ровно по одной клетке с точкой, и, когда обоими игроками в сумме будут сделаны ходов, все клетки с точками будут окрашены, причём не меньше половины из них будут окрашены Васей, а Петя больше не сможет сделать ни одного хода.
После остановки Пети оставшиеся клетки окрасит Вася. Следовательно, при чётном Петя в любом случае сможет окрасить не больше
клеток, что составляет ровно половину от всех клеток доски только при и чётном , и меньше половины при . Следовательно, если делится нацело на и , где — чётно, то Петя может сделать максимум ничью. Такими будут и .
Стратегия Пети для достижения ничьи: Петя должен красить в точности только те «отмеченные» квадраты размера на клеток, на которые доска была разделена с самого начала, и не пропускать свой ход. Тогда он и Вася своими ходами исключают из дальнейшего использования Петей ровно по одному (а не больше) отмеченному квадрату на и Петя сможет сделать ровно результативных ходов и окрасить в синий цвет половину всех клеток доски. При проверке нужно особенно внимательно следить за изложением стратегии Пети по достижению ничьей.
При нечётном Петя в любом случае сможет окрасить не больше
клеток, что составляет меньше половины от всех клеток доски. Поэтому для нечётного Петя в любом случае проиграет.