В квадрате 11 ×11 отметили чётное число клеток. Оказалось, что в любом квадрате 2 × 2 также отмечено чётное число клеток. Докажите, что на каждой из главных диагоналей большого квадрата отмечено чётное число клеток.
Краткий ответ: будем считать числа по модулю \(2\). Условие про каждый квадрат \(2\times2\) позволяет представить клетку в виде \[ a_{ij}=r_i+c_j \pmod 2. \] Тогда число отмеченных клеток на каждой главной диагонали имеет ту же чётность, что и число отмеченных клеток во всём квадрате. Оно чётное, значит, обе диагонали содержат чётное число отмеченных клеток.
Доказательство
Обозначим \[ a_{ij}= \begin{cases} 1,&\text{если клетка отмечена},\\ 0,&\text{если не отмечена}. \end{cases} \]
Для любого квадрата \(2\times2\) сумма его четырёх чисел чётна: \[ a_{ij}+a_{i+1,j}+a_{i,j+1}+a_{i+1,j+1}\equiv0\pmod2. \]
Из этого условия следует, что существуют числа \(r_i\) и \(c_j\), для которых \[ a_{ij}\equiv r_i+c_j\pmod2. \] Например, можно взять \[ r_i=a_{i1},\qquad c_j=a_{1j}+a_{11}. \] Условие на квадраты \(2\times2\) гарантирует, что эта формула верна для всех клеток.
Пусть \(T\) — общее число отмеченных клеток. Тогда \[ T\equiv\sum_{i=1}^{11}\sum_{j=1}^{11}(r_i+c_j)\pmod2. \] Каждое \(r_i\) встречается \(11\) раз и каждое \(c_j\) — тоже \(11\) раз. Так как \(11\) нечётно, \[ T\equiv \sum_{i=1}^{11}r_i+\sum_{j=1}^{11}c_j\pmod2. \]
Для первой главной диагонали: \[ \sum_{i=1}^{11}a_{ii} \equiv\sum_{i=1}^{11}(r_i+c_i) \equiv\sum r_i+\sum c_i \equiv T\equiv0\pmod2. \]
Для второй главной диагонали: \[ \sum_{i=1}^{11}a_{i,12-i} \equiv\sum_{i=1}^{11}(r_i+c_{12-i}) \equiv\sum r_i+\sum c_j \equiv T\equiv0\pmod2. \]
Следовательно, на каждой из главных диагоналей отмечено чётное число клеток. ∎
Обсуждение
2 сообщенияВ квадрате 11 ×11 отметили чётное число клеток. Оказалось, что в любом квадрате 2 × 2 также отмечено чётное число клеток. Докажите, что на каждой из главных диагоналей большого квадрата отмечено чётное число клеток.
Обозначим через \(a_{ij}\) число \(0\) или \(1\):
\[ a_{ij}= \begin{cases} 1,&\text{если клетка отмечена},\\ 0,&\text{иначе}. \end{cases} \]
Все дальнейшие равенства рассматриваем по модулю \(2\).
1. Свойство четырёх углов прямоугольника
Если сложить условия для всех квадратов \(2\times2\) внутри прямоугольника с углами \((1,1)\), \((1,j)\), \((i,1)\), \((i,j)\), то все внутренние клетки сократятся по модулю \(2\). Останется:
\[ a_{11}+a_{1j}+a_{i1}+a_{ij}=0. \]
Значит,
\[ a_{ij}=a_{i1}+a_{1j}+a_{11}. \tag{1} \]
2. Сравним диагонали с общим числом отмеченных клеток
Пусть \(S\) — число отмеченных клеток во всём квадрате. Из (1):
\[ S\equiv 11\sum_{i=1}^{11}a_{i1} +11\sum_{j=1}^{11}a_{1j} +11^2a_{11}. \]
Так как \(11\) нечётно, получаем
\[ S\equiv \sum_{i=1}^{11}a_{i1} +\sum_{j=1}^{11}a_{1j} +a_{11}. \tag{2} \]
Для первой главной диагонали:
\[ \sum_{i=1}^{11}a_{ii} \overset{(1)}{\equiv} \sum_{i=1}^{11}(a_{i1}+a_{1i}+a_{11}) \equiv \sum_{i=1}^{11}a_{i1} +\sum_{i=1}^{11}a_{1i} +a_{11}. \]
По формуле (2) это сравнимо с \(S\).
Для второй главной диагонали:
\[ \sum_{i=1}^{11}a_{i,\,12-i} \overset{(1)}{\equiv} \sum_{i=1}^{11}(a_{i1}+a_{1,\,12-i}+a_{11}). \]
Индексы \(12-i\) пробегают все числа от \(1\) до \(11\), поэтому это выражение также сравнимо с \(S\).
Следовательно, число отмеченных клеток на каждой диагонали имеет ту же чётность, что и общее число отмеченных клеток. Общее число чётно, значит, на каждой из главных диагоналей отмечено чётное число клеток. \(\square\)
