|
|
 |
Условие
Имеется таблица n×n, в n – 1 клетках которой записаны единицы, а в остальных клетках – нули. С таблицей разрешается проделывать следующую операцию: выбрать клетку, вычесть из числа, стоящего в этой клетке, единицу, а ко всем остальным числам, стоящим в одной строке или в одном столбце с выбранной клеткой, прибавить единицу. Можно ли из этой таблицы с помощью указанных операций получить таблицу, в которой все числа равны?
Решение
Докажем, что в исходной таблице найдётся подтаблица 2×2, в которой стоит одна единица и три нуля.
Найдется строка, в которой стоят одни нули (так как строк n, а единиц n – 1). Очевидно, что в таблице найдутся две соседние строки, в одной из которых стоят все нули, а в другой по крайней мере одна единица. В этой ненулевой строке найдутся две соседние клетки, в одной из которых стоит единица, а в другой – ноль. Эти две клетки и две соседние клетки из нулевой строки образуют искомую подтаблицу.
Выберем в нашей таблице произвольную подтаблицу 2×2: пусть в ее левом верхнем углу стоит число a, в правом верхнем – b, в левом нижнем – c и в правом нижнем – d, а после проведения операции – a1, b1, c1, d1 соответственно. Рассмотрим выражения
D = (a + d) – (b + c) и D1 = (a1 + d1) – (b1 + c1). Возможны три случая.
1) Выбранная клетка находится вне нашей подтаблицы, но лежит в строке или столбце, пересекающем нашу подтаблицу. Пусть для определенности она лежит в одной строке c a и b, тогда a1 = a + 1, b1 = b + 1, c1 = c, d1 = d и D1 = (a + 1 + d) – (b + 1 + c) = D.
2) Выбранная клетка находится вне нашей подтаблицы, и при этом она не лежит ни в строке, ни в столбце, пересекающем нашу таблицу. Тогда, очевидно, D1 = D.
3) Выбранная клетка находится внутри нашей подтаблицы. Пусть для определенности она – верхняя левая клетка подтаблицы, тогда a1 = a – 1, b1 = b + 1, c1 = c + 1, d1 = d и D1 = D – 3. (Если правая нижняя, то опять D1 = D – 3, в противном случае D1 = D + 3.)
Таким образом, мы показали, что остаток от деления D на 3 – инвариант. Однако в исходной таблице мы нашли подтаблицу 2×2, в которой D = ±1, а мы должны получить таблицу, в которой все числа равны, то есть с D = 0, что невозможно.
Ответ
Нельзя.
