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

Маша шахмат тақтасын бояп жаттығады. Бір жүрісте ол тақтаның бұрышына іргелес кез келген тіктөртбұрышты тақтаның барлық шаршыларын қарама-қарсы түске өзгертеді. Осындай амал қолданып, ол шахмат тақтасының шаршыларын бірдей түске бояй ала ма?

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

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

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