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

Маша упражняется в перекрашивании шахматной доски. За один раз она может изменить цвет каждой клетки в любом прямоугольнике, прилегающем к углу доски. Получится ли у неё с помощью таких операций перекрасить всю доску в один цвет?

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

Комментарии от администратора Комментарии от администратора №1.     Ответ. Получится.
Решение 1. Первое решение. Пронумеруем клетки доски: в верхней горизонтали слева направо номерами от 1 до 8, во второй сверху — слева направо номерами от 9 до 16 и т.д. Пусть клетка в правом нижнем углу — белая. Пусть $n$ — наибольший номер черной клетки. Возьмем черную клетку $K$ с этим номером и перекрасим все клетки прямоугольника, у которого одна из вершин — левая верхняя вершина доски, а вторая — правая нижняя вершина клетки $K$. Ни одна из клеток с номерами, большими $n$, в нем не лежит, так как все они правее или ниже $K$. Поэтому наибольший номер черной клетки после такой перекраски уменьшится. Поскольку такое уменьшение может происходить лишь конечное (не большее 63) число раз, мы, повторяя описанную процедуру, в конце концов получим белую доску.

Комментарии от администратора Комментарии от администратора №2.     Ответ. Получится.
Решение 2. Второе решение. Перекрасим первый столбец, потом прямоугольники из первого и второго столбцов, из первого, второго и третьего столбцов, $\dots$, из 1-7 столбцов. Затем перекрасим первую строку, затем прямоугольники из первой и второй строк, из первой, второй и третьей строк, $\dots$, из 1-7 строк. Нетрудно проверить, что после этого все клетки того же цвета, что и клетка на пересечении первой строки и первого столбца, перекрасятся четное число раз, а все клетки противоположного цвета — нечетное число раз, так что вся доска окрасится в цвет клетки на пересечении первой строки и первого столбца.