В квадрате 11 ×11 отметили чётное число клеток. Оказалось, что в любом квадрате 2 × 2 также отмечено чётное число клеток. Докажите, что на каждой из главных диагоналей большого…
В квадрате 11 ×11 отметили чётное число клеток. Оказалось, что в любом квадрате 2 × 2 также отмечено чётное число клеток. Докажите, что на каждой из главных диагоналей большого квадрата отмечено чётное число клеток.
Пусть \(a_{ij}=1\), если клетка отмечена, и \(0\) иначе (по модулю \(2\)).
Из условия для каждого \(2\times2\): \[ a_{ij}+a_{i,j+1}+a_{i+1,j}+a_{i+1,j+1}=0. \] Следовательно, \[ a_{ij}=x_i+y_j \pmod 2. \]
Тогда для главных диагоналей: \[ \sum_{i=1}^{11}a_{ii} \equiv \sum x_i+\sum y_i, \] \[ \sum_{i=1}^{11}a_{i,12-i} \equiv \sum x_i+\sum y_{12-i} \equiv \sum x_i+\sum y_i. \]
А общее число отмеченных клеток: \[ \sum_{i,j}a_{ij} \equiv 11\sum x_i+11\sum y_j \equiv \sum x_i+\sum y_i\equiv0, \] так как \(11\) нечётно и общее число клеток чётно.
Значит, на обеих главных диагоналях отмечено чётное число клеток.
Обсуждение
4 сообщенияРеши проще
Решим только по чётности.
Обозначим отмеченную клетку числом \(1\), а неотмеченную — \(0\).
1. Как связаны соседние строки
Рассмотрим две соседние строки. Для любых двух соседних столбцов в квадрате \(2\times2\) число единиц чётно, поэтому \[ a_j+a_{j+1}\equiv b_j+b_{j+1}\pmod 2. \] Значит, если в первом столбце строки совпадают или различаются, то это верно и во всех остальных столбцах.
Следовательно, каждая строка либо:
- полностью совпадает с первой строкой;
- полностью противоположна первой строке.
Пусть первая строка имеет вид \(a_1,\ldots,a_{11}\), а \(t_i=0\), если \(i\)-я строка совпадает с первой, и \(t_i=1\), если противоположна. Тогда клетка \((i,j)\) имеет значение \[ a_j+t_i\pmod2. \]
2. Чётность диагоналей
На главной диагонали число отмеченных клеток имеет чётность \[ (a_1+\cdots+a_{11})+(t_1+\cdots+t_{11}). \]
На другой диагонали получается то же самое, только \(a_1,\ldots,a_{11}\) идут в обратном порядке. Значит, обе диагонали имеют одинаковую чётность.
Кроме того, во всём квадрате чётность числа отмеченных клеток равна \[ 11(a_1+\cdots+a_{11})+11(t_1+\cdots+t_{11}), \] то есть, поскольку \(11\) нечётно, \[ (a_1+\cdots+a_{11})+(t_1+\cdots+t_{11}). \]
По условию общее число отмеченных клеток чётно. Значит, эта сумма равна \(0\pmod2\). Следовательно, на каждой из двух главных диагоналей отмечено чётное число клеток.
Не понятно
Давай совсем по шагам, без сложных формул.
1. Какие бывают соседние строки?
Рассмотрим любые две соседние строки.
В каждом квадрате \(2\times2\) число отмеченных клеток чётное. Поэтому в двух соседних столбцах отношение между клетками верхней и нижней строки одинаковое:
- если в одном столбце клетки отмечены одинаково, то и в соседнем — одинаково;
- если в одном столбце одна клетка отмечена, а другая нет, то и в соседнем — так же.
Значит, две соседние строки либо:
- полностью одинаковы;
- полностью противоположны: где в одной отмечена клетка, там в другой не отмечена.
Следовательно, относительно первой строки любая строка либо такая же, либо противоположная.
2. Посчитаем чётность диагонали
Пусть в первой строке отмечено \(k\) клеток. Пусть \(q\) строк противоположны первой.
На любой главной диагонали берётся по одной клетке из каждой строки, причём используются все \(11\) столбцов.
Если строка такая же, как первая, она сохраняет чётность числа отмеченных клеток. Если противоположная — меняет её. Поэтому чётность числа отмеченных клеток на каждой диагонали равна чётности \[ k+q. \]
Это верно для обеих диагоналей.
3. Используем условие про весь квадрат
Одинаковая с первой строка содержит \(k\) отмеченных клеток.
Противоположная строка содержит \(11-k\) клеток. Числа \(k\) и \(11-k\) имеют разную чётность, потому что \(11\) нечётно.
Значит, чётность общего числа отмеченных клеток также равна чётности \[ k+q. \]
По условию общее число отмеченных клеток чётное. Значит, \(k+q\) — чётное число.
Следовательно, на каждой из двух главных диагоналей отмечено чётное число клеток. \(\square\)
