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

Петя и Вася играют на клетчатой доске $20 \times 20$. Каждым ходом игрок выбирает клетку, у которой все 4 стороны не окрашены, и красит все стороны в красный и синий цвета в любом порядке (например, может покрасить все в один цвет). При этом не должно получаться отрезков одного цвета длиной более чем одна сторона клетки. Проигрывает тот, кто не может сделать ход. Первым ходит Петя. Кто из игроков может выигрывать, как бы ни играл соперник?

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

Комментарии от администратора Комментарии от администратора №1.     Ответ. Выигрывает Вася.
Решение. Вася разбивает все клетки доски на пары центрально симметричных, и ответным ходом красит стороны клетки из той же пары так, чтобы центрально симметричные стороны были покрашены в разные цвета. Пока Васина стратегия действует, после его хода в каждой паре центрально симметричных сторон либо обе стороны окрашены в разные цвета, либо обе стороны не окрашены. Докажем, что Вася всегда может сделать ход. Во-первых, у центрально симметричных клеток нет общих сторон. Поэтому Петя, делая ход, не сможет одновременно окрасить две центрально симметричных стороны. Во-вторых, если 4 окрашенные Петей стороны ограничивают клетку, то и 4 центрально симметричные им стороны тоже ограничивают клетку, и все они не окрашены. Вася может их красить. Покажем, что, действуя по стратегии, Вася не образует запрещённых одноцветных отрезков. Пусть покрашенная Васей сторона $AB$ продолжила уже покрашенную сторону $BC$. Если $B$ — центр доски, то стороны $AB$ и $BC$ центрально симметричны, и покрашены по Васиной стратегии в разные цвета. Иначе $ AB$ и $BC$ центрально симметричны сторонам $A’B’$ и $B’C’$, при этом Петя предыдущим ходом смог покрасить сторону $A’B’$, значит, $A’B’$ и $B’C’$ — разного цвета. При смене цветов на противоположные они останутся разного цвета, так что $AB$ и $BC$ — разного цвета, и отрезок $AC$ не запрещён. Итак, по указанной стратегии Вася может всегда сделать ход, поэтому он не проиграет. А так как доска конечна и игра закончится, Вася выиграет.