Олимпиада имени Леонарда Эйлера2014-2015 учебный год, III тур дистанционного этапа

Двое играют в такую игру. За один ход можно положить в одну из клеток квадратной доски $1001 \times 1001$ один камешек (первоначально доска пуста; в одной клетке может лежать любое число камешков). Ходят по очереди. Как только в каком-то ряду (вертикали или горизонтали) оказывается более 5 камешков, сделавший последний ход признается проигравшим. Кто из игроков сможет выиграть независимо от действий соперника: тот, кто делает первый ход или тот, кто ходит вторым?

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. Первый.
Решение 1. До того, как на доску выложен 5005-ый камешек, первый находит строку и столбец, в которых находится менее пяти камешков (такие обязательно найдутся), и кладёт камешек в клетку на их пересечении. Если второй не ошибся раньше, после того, как на доску будет положен 5005-ый камешек (а его, как и все нечётные, положит первый), мы приходим к ситуации, в которой в каждой строке и каждом столбце лежит ровно по 5 камешков. В ней второй проигрывает, какой бы ход он ни сделал.

Комментарии от администратора Комментарии от администратора №2.     Ответ. Первый.
Решение 2. Пусть первым ходом первый положит камешек в цен-тральную клетку доски, а затем кладет каждый свой камешек симметрично относительно центра доски последнему камешку соперника. Тогда если первый делает ход в строку или столбец, содержащий центральную клетку, там после этого хода будет нечетное числу камешков, а если камешек первого оказался в строке или столбце, не содержащем центральную клетку, там после его хода станет столько же камешков, сколько в симметричной относительно центра доски строке (столбце). Таким образом, если после хода первого в какой-то строке или каком-то столбце оказалось больше 5 камешков, то и до его хода были строка или столбец, где находилось больше 5 камешков. Значит, первый при такой игре не может проиграть, а так как игра конечна, то второй рано или поздно проиграет.