Раскраска каркаса

[Roman Kotyk]

Некоторые стороны клеток на доске ($8\times 8$) окрашены в красный цвет, а другие – в синий цвет. Разрешается произвольно выбирать клетку доски и перекрашивать все ее стороны одновременно в противоположный цвет. Всегда ли можно сделать несколько перекрашиваний так, чтобы синих стало меньше $\frac 14$ от всего количества сторон клеток?

[maxmatem]

Roman Kotyk

А допускается, что какая то клетка имеет имеет все стороны одного цвета?

[Roman Kotyk]

Насколько я понял условие - допускается!

[iancaple]

Всего ребер $144$. Пусть раскраска такова, что синими являются верх и низ каждой клетки вертикалей a,c,e,g , и только они, ровно $\frac 14$ синих. Любая последовательность перекрашиваний сводится к выделению множества $M$ тех клеток , которые перекрашивались нечетное число раз, так как операции перекрашивания перестановочны, и два перекрашивания с центром в одной клетке = ни одного. Выделим во множестве $M$ связные компоненты, по которым может гулять ладья. Границы этих компонент- непересекающиеся (по ребрам) циклы на графе из ребер, и в каждом цикле не более половины изначально синих ребер (синие не имели общих вершин). Значит, при одновременном изменении цвета всех ребер каждого цикла (к чему сводится вся последовательность перекрашиваний), число синих ребер не уменьшится.