Задача 109646
|
|
 |
Условие
Квадрат n×n ( nРешение
Докажем утверждение от противного. Пусть есть раскраска, при которой отсутствует пара параллельных линий с одинаковым числом черных клеток.Будем называть весом линии количество черных клеток на ней. Пусть есть горизонталь веса n . Тогда n вертикалей и n диагоналей каждого направления должны иметь веса 1, 2, n , так как все они пересекают эту горизонталь. Тогда и n горизонталей имеют веса 1, 2, n , так как все они пересекают вертикаль веса n .
Циклически переставим горизонтали и вертикали так, чтобы нижняя горизонталь и левая вертикаль имели вес n (свойства раскраски при этом не изменятся). Пронумеруем горизонтали снизу вверх от 0 до n-1 , а вертикали – от 0 до n-1 слева направо.
Каждая диагональ пересекает по разу горизонталь и вертикаль веса n ; поэтому диагонали веса 1 должны проходить через клетку их пересечения – клетку (0,0) . Итак, все клетки (i,i) и (n-i,i) , i>0 , не закрашены.
Если n нечетно, то в каждом столбце, кроме 0, получаем не менее двух незакрашенных клеток, и столбца веса n-1 не найдется.
Если n=2m , то столбец m и строка m должны иметь вес n-1 (в любой из остальных строк и любом из остальных столбцов есть хотя бы две незакрашенные клетки). Тогда в них закрашены все клетки, кроме (m,m) , и мы не сможем найти столбца веса 1.
Если с самого начала отсутствует горизонталь веса n , то есть горизонталь веса 0, и мы можем провести те же рассуждения, поменяв ролями закрашенные и незакрашенные клетки.
