Разделы 
Дополнительно
Задача по математике - 1548
2019-01-19 
Имеется таблица $n \times n$, в $n - 1$ клетках которой записаны единицы, а в остальных клетках - нули. С таблицей разрешается проделывать следующую операцию: выбрать клетку, вычесть из числа, стоящего в этой клетке, единицу, а ко всем остальным числам, стоящим в одной строке или в одном столбце с выбранной клеткой, прибавить единицу. Можно ли из этой таблицы с помощью указанных операций получить таблицу, в которой все числа равны?
Решение:
1) Докажем, что в исходной таблице найдется подтаблица $2 \times 2$, в которой стоит одна единица и три нуля. По принципу Дирихле найдется строка, в которой стоят одни нули (так как строк $n$, а единиц $n - 1$). Очевидно, что в таблице найдутся две соседние строки, в одной из которых стоят все нули, а в другой по крайней мере одна единица. Действительно, если бы такого не было, рядом с найденной строкой со всеми нулями стояли бы строки тоже со всеми нулями, и т. д., т. е. в таблице были бы одни нули - противоречие. Аналогично предыдущему получаем, что в ненулевой строке найдутся две соседние клетки, в одной из которых стоит единица, а в другой - ноль. Эти две клетки и две соседние клетки из нулевой строки образуют искомую подтаблицу.
2) Выберем в нашей таблице произвольную подтаблицу $2 \times 2$: пусть в ее левом верхнем углу стоит число $а$, в правом верхнем - $b$, в левом нижнем - $с$ и в правом нижнем - $d$, а после проведения операции - $а_1, b_1, с_1, d_1$ соответственно.
Рассмотрим выражения $D = (а + d) - (b + с)$ и $D_1 = (а_1 + d_1) - (b_1 + с_1)$. Возможны три случая:
а) Выбранная клетка находится вне нашей подтаблицы, и при этом она лежит в строке или столбце, пересекающем нашу подтаблицу. Пусть для определенности она лежит в одной строке с $а$ и $b$, тогда $а_1 = а +1, b_1 = b + 1, С_1 = с, d_1 = d$ и $D_1 = (а + 1 + d) - (b + 1 + с) = а + d - b - с + 1 - 1 = D$.
б) Выбранная клетка находится вне нашей подтаблицы, и при этом она не лежит ни в строке, ни в столбце, пересекающем нашу таблицу. Тогда $а_1 = а, b_1 = b, с_1 = с, d_1 = d$ и $D_1 = (а + d) - (b + с) = а + d - b - с = D$.
в) Выбранная клетка находится внутри нашей подтаблицы. Пусть для определенности она - верхняя левая клетка подтаблицы, тогда $а_1 = а - 1, b_1 = b + 1, с_1 = с + 1, d_1 = d$ и $D_1 = (а - 1 + d) - (b + 1 + с +1) = а + d - b - с - 1 - 1 - 1 = D - 3$. (Если правая нижняя, то опять $D_1 = D - 3$, в противном случае $D_1 \equiv D + 3$). Таким образом, мы показали, что $D_1 \equiv D (mod 3)$ (для любого количества операций). Однако в исходной таблице мы нашли подтаблицу $2 \times 2$, в которой $D$ равно либо 1, либо -1, т. е. $D \equiv 1 (mod 3)$ или $D = 2 (mod 3)$, а мы должны получить таблицу, в которой все числа равны, т. е. с $D \equiv 0 (mod 3)$.
Ответ. Нельзя.
Имеется таблица $n \times n$, в $n - 1$ клетках которой записаны единицы, а в остальных клетках - нули. С таблицей разрешается проделывать следующую операцию: выбрать клетку, вычесть из числа, стоящего в этой клетке, единицу, а ко всем остальным числам, стоящим в одной строке или в одном столбце с выбранной клеткой, прибавить единицу. Можно ли из этой таблицы с помощью указанных операций получить таблицу, в которой все числа равны?
Решение:
1) Докажем, что в исходной таблице найдется подтаблица $2 \times 2$, в которой стоит одна единица и три нуля. По принципу Дирихле найдется строка, в которой стоят одни нули (так как строк $n$, а единиц $n - 1$). Очевидно, что в таблице найдутся две соседние строки, в одной из которых стоят все нули, а в другой по крайней мере одна единица. Действительно, если бы такого не было, рядом с найденной строкой со всеми нулями стояли бы строки тоже со всеми нулями, и т. д., т. е. в таблице были бы одни нули - противоречие. Аналогично предыдущему получаем, что в ненулевой строке найдутся две соседние клетки, в одной из которых стоит единица, а в другой - ноль. Эти две клетки и две соседние клетки из нулевой строки образуют искомую подтаблицу.
2) Выберем в нашей таблице произвольную подтаблицу $2 \times 2$: пусть в ее левом верхнем углу стоит число $а$, в правом верхнем - $b$, в левом нижнем - $с$ и в правом нижнем - $d$, а после проведения операции - $а_1, b_1, с_1, d_1$ соответственно.
Рассмотрим выражения $D = (а + d) - (b + с)$ и $D_1 = (а_1 + d_1) - (b_1 + с_1)$. Возможны три случая:
а) Выбранная клетка находится вне нашей подтаблицы, и при этом она лежит в строке или столбце, пересекающем нашу подтаблицу. Пусть для определенности она лежит в одной строке с $а$ и $b$, тогда $а_1 = а +1, b_1 = b + 1, С_1 = с, d_1 = d$ и $D_1 = (а + 1 + d) - (b + 1 + с) = а + d - b - с + 1 - 1 = D$.
б) Выбранная клетка находится вне нашей подтаблицы, и при этом она не лежит ни в строке, ни в столбце, пересекающем нашу таблицу. Тогда $а_1 = а, b_1 = b, с_1 = с, d_1 = d$ и $D_1 = (а + d) - (b + с) = а + d - b - с = D$.
в) Выбранная клетка находится внутри нашей подтаблицы. Пусть для определенности она - верхняя левая клетка подтаблицы, тогда $а_1 = а - 1, b_1 = b + 1, с_1 = с + 1, d_1 = d$ и $D_1 = (а - 1 + d) - (b + 1 + с +1) = а + d - b - с - 1 - 1 - 1 = D - 3$. (Если правая нижняя, то опять $D_1 = D - 3$, в противном случае $D_1 \equiv D + 3$). Таким образом, мы показали, что $D_1 \equiv D (mod 3)$ (для любого количества операций). Однако в исходной таблице мы нашли подтаблицу $2 \times 2$, в которой $D$ равно либо 1, либо -1, т. е. $D \equiv 1 (mod 3)$ или $D = 2 (mod 3)$, а мы должны получить таблицу, в которой все числа равны, т. е. с $D \equiv 0 (mod 3)$.
Ответ. Нельзя.
