Задача 110080

Темы:    [ Выигрышные и проигрышные позиции ] [ Симметричная стратегия ] [ Геометрия на клетчатой бумаге ]

Сложность: 4- Классы: 7,8,9

Условие

Автор: Храмцов Д.

Уголком размера n×m , где m,n2 , называется фигура, получаемая из прямоугольника размера n×m клеток удалением прямоугольника размера (n-1)×(m-1) клеток. Два игрока по очереди делают ходы, заключающиеся в закрашивании в уголке произвольного ненулевого количества клеток, образующих прямоугольник или квадрат. Пропускать ход или красить одну клетку дважды нельзя. Проигрывает тот, после чьего хода все клетки уголка окажутся окрашенными. Кто из игроков победит при правильной игре?

Решение

Укажем выигрышную стратегию для первого игрока.

Можно считать, что m n .

Если m=2 , то первый своим ходом красит всю большую сторону уголка, оставляя второму одну клетку, и выигрывает.

Далее считаем n m3 .
В этом случае первый красит на большей стороне n-m+1 клетку, начиная с угловой, после чего остается две одинаковых полоски по m-1 клетке.
Далее первый игрок симметрично повторяет в другой полоске ходы второго, сделанные в одной из полосок, до тех пор, пока после хода второго не останется единственного незакрашенного прямоугольника из более чем одной клетки.

Затем, если число незакрашенных одноклеточных прямоугольников к этому моменту нечетно, то первый красит неодноклеточный прямоугольник целиком, а если четно, то оставляет в нем одну незакрашенную клетку.

Таким образом, после его хода останется нечетное количество некрашенных прямоугольников, каждый из которых одноклеточный, поэтому последний ход вынужден будет сделать второй игрок, в результате чего и проиграет.

Ответ

При любых n и m победит первый игрок.

Источники и прецеденты использования

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	2001
Этап
Вариант	4
Класс
Класс	8
задача
Номер	01.4.8.4