Олимпиадная задача: Кто победит в закрашивании уголка n×m? Комбинаторная геометрия, 7-9 класс, Храмцов Д.
Задача
Уголком размера n×m , где m,n
2, называется фигура, получаемая из
прямоугольника размераn×mклеток удалением прямоугольника
размера (n-1)×(m-1) клеток.
Два игрока по очереди делают ходы, заключающиеся в закрашивании в уголке
произвольного ненулевого количества клеток, образующих прямоугольник или квадрат.
Пропускать ход или красить одну клетку дважды нельзя. Проигрывает тот, после
чьего хода все клетки уголка окажутся окрашенными. Кто из игроков победит при
правильной игре?
Решение
Укажем выигрышную стратегию для первого игрока.
Можно считать, что m
n .
Если m=2, то первый своим ходом красит всю большую сторону уголка, оставляя второму одну клетку, и выигрывает.
Далее считаем n m3.
В этом случае
первый красит на большей стороне n-m+1 клетку, начиная с угловой, после чего
остается две одинаковых полоски по m-1 клетке.
Далее первый игрок симметрично
повторяет в другой полоске ходы второго, сделанные в одной из полосок, до тех
пор, пока после хода второго не останется единственного незакрашенного
прямоугольника из более чем одной клетки.
Затем, если число незакрашенных одноклеточных прямоугольников к этому моменту нечетно, то первый красит неодноклеточный прямоугольник целиком, а если четно, то оставляет в нем одну незакрашенную клетку.
Таким образом, после его хода останется нечетное количество некрашенных прямоугольников, каждый из которых одноклеточный, поэтому последний ход вынужден будет сделать второй игрок, в результате чего и проиграет.
Ответ
При любых n и m победит первый игрок.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь