Задание №178063: Турнир Ломоносова 2008

2. «Хамелеон». Пункты «а» и «в» (как и в предыдущей задаче,
собственно) давались для того, чтобы участники, которым трудно сразу
же рассуждать для больших n, попробовали почувствовать стратегию
на небольшом поле. Мы приведём решение сразу пунктов «б» и «г».
В пункте «б» при достаточно большом n побеждает первый игрок.
Он ставит ладью на самое левое поле второй горизонтали сверху и объ
являет её конём. У соперника в этом случае только один ход (на третье
слева поле верхней горизонтали), более того, у него после этого хода

35

нет выбора — он обязан объявлять коня ладьёй. Как только это проис
ходит, первый игрок побеждает. Описанная стратегия «работает» при
n > 3. Меньшие значения n нетрудно разобрать непосредственно, там
побеждает второй игрок: случай n = 1, пожалуй, можно считать некор
ректным, при n = 2 ходы игроков предопределены, при n = 3 у первого
игрока по сути есть два различных хода, после которых объявлять хаме
леона конём для него либо невозможно, либо глупо, а если он оставит
его ладьёю, то второй игрок либо сразу победит, либо поставит ладью
в центральную клетку, после чего ситуация сведётся к случаю n = 2.
Эта, стратегия, заметим, в целом решает и ту часть пункта «д»,
которая относится к случаю, когда хамелеон вначале ладья. При
min(m,n) > 3 она применяется так же, в случае min(m,n) = 1 первый
побеждает сразу, а при min(m,n) = 2 или при min(m,n) = 3 первый
игрок сводит поле к 2 × 2 или 3 × 3, где и побеждает, так как он теперь
как бы второй. Итак, новых исключений неквадратные поля не доба
вили.
В пункте «г» при достаточно большом n побеждает второй игрок.
Его стратегия заключается в том, что на любой ход первого игрока
он: если хамелеон стал ладьёй, выигрывает согласно разобранной части
пункта «д»; если хамелеон остался конём, возвращает его на большую
диагональ, идущую из нижнего левого угла доски, и сохраняет его
конём. При этом поле n × n редуцируется до поля (n − 3) × (n − 3).
Так можно делать до тех пор, пока n (cid:62) 4. В конце нужно правильно
разыграть эндшпиль: когда после очередной редукции n −→ (n − 3) мы
придём к n = 2 или n = 3, нужно не оставлять хамелеона конём, а сде
лать его ладьёй, поскольку, как мы уже видели в решении пункта «б»,
это приведёт второго игрока к выигрышу.
От пункта «д» нам осталось разобрать случай, когда в начале игры
на произвольном поле хамелеон является конём. Это можно сделать
методом выигрышных и проигрышных позиций, о которых мы уже гово
рили в задаче № 1. Рассмотрим «бесконечную влево-вниз» доску и будем
ставить в клетке с координатами (m; n) букву «В», если, начиная с этой
клетки конём, мы побеждаем, и букву «П» в противном случае. Клетки
1 × n, n × 1 и 2 × 2 пометим буквой «Н» — начинать игру конём в этих
клетках нельзя по правилам.
Постепенно заполняя таблицу, увидим, что начинающий проиг
рает на полях размером (3k − 1) × (3k + p) (k — любое натуральное
число, p — любое натуральное большее единицы), полях размером
(3k) × (3k + 2) и квадратных полях n × n при n > 2. На всех остальных
полях начинающий конём победит.
36

... 8 7 6 5 4 3 2 1
Н Н Н Н Н Н Н Н Н 1
П П П П П П В Н Н 2
В В В В П В П В Н 3
В В В В В П В П Н 4
П П П В П В П П Н 5

В П В П В В В П Н 6
В В П В П В В П Н 7
В П В П П В В П Н 8
П В В В П В В П Н ...

Анализ выигрышных и проигрышных полей помогает разобраться и
с пунктом «е». Ограничимся в этом пункте только сообщением ответа.
Хамелеон-ладья даёт победу начинающему на всех полях, кроме 1 × 1 и
2 × 2, а хамелеон-конь — на всех белых полях (считаем, что доска шах
матно раскрашена и угловая клетка чёрная), кроме 1 × 2, где хамелеон
не может начинать игру как конь.
Критерии проверки. За пункт «а» давался 1 балл, за «б» — 3
балла (один снимался, если не разбирались случаи малых n), за «в» —
3 балла, за «г» — 5 баллов (один балл снимался, как и в «б»), прозе
вавшим малые n), за «д» и «е» — по 4 балла (2 «за ладью» и 2 «за
коня»). В последних двух пунктах считалось достаточным нарисовать
таблички или внятно описать их. «Голые» ответы не оценивались.