В квадрате 11 ×11 отметили чётное число клеток. Оказалось, что в любом квадрате 2 × 2 также отмечено чётное число клеток. Докажите, что на каждой из главных диагоналей большого…
В квадрате 11 ×11 отметили чётное число клеток. Оказалось, что в любом квадрате 2 × 2 также отмечено чётное число клеток. Докажите, что на каждой из главных диагоналей большого квадрата отмечено чётное число клеток.
Краткий ответ: обе главные диагонали имеют ту же чётность, что и все отмеченные клетки. Так как всего отмечено чётное число клеток, на каждой диагонали также чётное число отмеченных клеток.
Доказательство
Будем считать только чётность: для клетки \(a_{ij}\) положим
\[ a_{ij}= \begin{cases} 1,&\text{если клетка отмечена},\\ 0,&\text{если не отмечена}. \end{cases} \]
Все суммы ниже рассматриваются по модулю \(2\).
Условие для любого квадрата \(2\times2\) означает:
\[ a_{ij}+a_{i+1,j}+a_{i,j+1}+a_{i+1,j+1}=0. \]
Если сложить такие равенства для всех квадратов \(2\times2\) внутри прямоугольника с углами \((1,1)\) и \((i,j)\), то все внутренние клетки сократятся: они встретятся чётное число раз. Останутся только четыре угловые клетки:
\[ a_{11}+a_{i1}+a_{1j}+a_{ij}=0. \]
Значит,
\[ a_{ij}=a_{i1}+a_{1j}+a_{11}. \]
Обозначим
\[ r_i=a_{i1},\qquad c_j=a_{1j}+a_{11}. \]
Тогда
\[ a_{ij}=r_i+c_j. \]
Пусть \(T\) — чётность общего числа отмеченных клеток. Так как размер квадрата равен \(11\times11\), а \(11\) — нечётное число,
\[ \begin{aligned} T &=\sum_{i=1}^{11}\sum_{j=1}^{11}a_{ij}\\ &=\sum_{i,j}(r_i+c_j)\\ &=11\sum_i r_i+11\sum_j c_j\\ &=\sum_i r_i+\sum_j c_j. \end{aligned} \]
Для первой главной диагонали:
\[ \sum_{i=1}^{11}a_{ii} =\sum_i(r_i+c_i) =\sum_i r_i+\sum_i c_i=T. \]
Для второй главной диагонали:
\[ \sum_{i=1}^{11}a_{i,\,12-i} =\sum_i(r_i+c_{12-i}) =\sum_i r_i+\sum_j c_j=T. \]
Следовательно, чётность каждой диагонали совпадает с чётностью общего числа отмеченных клеток. Общее число клеток отмечено чётно, поэтому на каждой из двух главных диагоналей отмечено чётное число клеток.
Обсуждение
2 сообщенияРеши проще
Решение
Рассмотрим две соседние строки. В каждой паре соседних столбцов стоит квадрат \(2\times2\).
Если в одном столбце эти две строки имеют одинаковые клетки, то и в следующем столбце они имеют одинаковые клетки; если разные — то тоже разные. Иначе в квадрате \(2\times2\) получилось бы нечётное число отмеченных клеток.
Значит, любые две соседние строки либо полностью совпадают, либо во всех клетках противоположны. Поэтому каждая строка либо такая же, как первая, либо получается из первой заменой отмеченных клеток на неотмеченные и наоборот.
Пусть в первой строке отмечено \(k\) клеток, а противоположных ей строк — \(p\).
- в обычной строке отмечено \(k\) клеток;
- в противоположной — \(11-k\) клеток.
Так как \(11\) нечётно, числа \(k\) и \(11-k\) имеют разную чётность. Поэтому чётность общего числа отмеченных клеток равна
\[ k+p \pmod 2. \]
Теперь посмотрим на главную диагональ. Если бы все строки совпадали с первой, на диагонали встретились бы все клетки первой строки по одному разу — то есть \(k\) отмеченных клеток. Каждая противоположная строка меняет чётность на \(1\). Значит, на диагонали чётность равна
\[ k+p \pmod 2. \]
На второй диагонали клетки первой строки также встречаются по одному разу, только в обратном порядке, поэтому чётность там тоже равна
\[ k+p \pmod 2. \]
Следовательно, обе диагонали имеют ту же чётность, что и общее число отмеченных клеток. Общее число чётное, значит, на каждой главной диагонали отмечено чётное число клеток.
