Математикадан Эйлер олимпиадасы, 2013-2014 оқу жылы, Дистанциялық кезеңнің 4-ші туры


Петя мен Вася $20 \times 20$ тақтасында ойнайды. Әр жүрісте ойыншы 4 қабырғасының ешқайсысы боялмаған $1 \times 1$ шаршы таңдап алып, оның қабырғаларын кез келген ретте қызыл және көк түске бояйды (мысалға, ол шаршының барлық қабырғаларын тек бір түске бояй алады). Сонымен қатар, әр жүрістен кейін бір түсті кесіндінің ұзындығы 1-ден ұзын болмауы керек. Кім келесі жүрісті жүре алмайды, сол ойыншы ұтылады. Дұрыс ойында кім жеңеді: бірінші ойыншы ма, әлде қарсыласы ма, және ұту үшін ол қалай ойнау керек?
посмотреть в олимпиаде

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

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