Раскраски

Рассмотрим ситуацию “за ход до проигрыша”, т. е. в которой невозможно сделать ход, чтобы не проиграть.

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

Итак, к этому моменту было сделано ходов. Покажем, что четно. Это будет означать, что в ситуации "за ход до проигрыша"может оказаться только Паша. Значит, у Вовы всегда есть ход, не ведущий к немедленному проигрышу, и поскольку игра завершится за конечное число ходов, Вова сможет победить.

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