Задача М847‍‍

а)Ответ: при правильной игре всегда побеждает игрок, ходящий вторым. Для этого он должен делать ходы, симметричные ходам первого (начинающего) относительно одной из диагоналей квадрата, пока первый не построит «почти-цикл», т. е. позицию, в которой достаточно обвести одну сторону, чтобы получился цикл (замкнутая ломаная). Обведя эту сторону, второй игрок выигрывает.

Нам надо доказать, что при такой стратегии первый «почти-цикл» не может возникнуть после хода второго игрока. Допустим, что, напротив, после того, как он обвёл некоторую сторону $a$‍,‍ впервые возник «почти-цикл», причём до цикла ему не достаёт одной стороны $b$‍;‍ пусть $x_1$‍,‍ $\ldots$‍,‍ $x_n$‍‍ — остальные стороны этого цикла. Эти стороны уже были обведены до последнего хода ($a$‍)‍ второго игрока, поэтому и симметричные им относительно диагонали стороны $x_1'$‍,‍ $\ldots$‍,‍ $x_n'$‍,‍ а также сторона $a'$‍,‍ симметричная $a$‍,‍ были обведены до этого хода. А так как $x_1$‍,‍ $\ldots$‍,‍ $x_n$‍‍ и $a$‍‍ образуют «почти-цикл», $x_1'$‍,‍ $\ldots$‍,‍ $x_n'$‍‍ и $a'$‍‍ тоже образуют «почти-цикл» (которому до цикла не достаёт стороны $b'$‍,‍ симметричной $b$‍).‍ Следовательно, «почти-цикл» возник перед последним ходом второго игрока. Противоречие.

б) Ответ: при чётном $n$‍‍ выигрывает второй игрок, при нечётном — первый; точнее, первый цикл образуется ровно через $(n+1)^2$‍‍ ходов (подразумевается, конечно, что игроки ходят правильно, т. е. не замыкают цикл, пока это возможно).

Действительно, рассмотрим позицию, в которой циклов ещё нет, но любой новый ход создаёт цикл. Мы докажем следующие два утверждения:

1) любые два узла «игрового поля» в этой позиции можно соединить цепочкой из обведённых сторон; другими словами, (разветвлённая) ломаная, составленная из всех обведённых сторон, проходит через все узлы и связна (из любой её вершины можно пройти по ней в любую другую вершину);

2) любая связная ломаная без циклов с $k$‍‍ вершинами имеет $k-1$‍‍ звеньев.

Из этих утверждений вытекает, что в рассматриваемой позиции обведено $(n+1)^2-1$‍‍ сторон, что нам и требуется.

Для доказательства первого утверждения возьмём любые два узла $A$‍‍ и $B$‍‍ и любую соединяющую их цепочку $c$‍‍ из сторон клеток. Пусть в ней встретилась необведённая сторона $XY$‍‍ (см. рисунок). Если её обвести, возникнет цикл. Очевидно, он должен содержать звено $XY$‍,‍ поэтому узлы $X$‍‍ и $Y$‍‍ уже должны быть соединены «мостиком» из обведённых сторон. Заменив каждое необведённое звено цепочки $c$‍‍ таким «мостиком», мы получим ломаную из обведённых сторон, проходящую через $A$‍‍ и $B$‍.‍

Рисунок к доказательству первого утверждения

Перейдём ко второму утверждению. Если ломаная не содержит циклов, то у неё, очевидно, имеется хотя бы одна вершина $X$‍,‍ из которой выходит только одно звено $XY$‍.‍ В силу связности, из точки $Y$‍‍ выходит ещё хотя бы одно звено. Удалим из ломаной звено $XY$‍;‍ вместе с ним удаляется одна вершина — $X$‍,‍ причём ломаная остаётся связной. Поступая так же и дальше, мы в конце концов получим одно звено. У этой «ломаной» число вершин на 1 больше числа звеньев, поэтому то же самое верно и для исходной ломаной.