Олимпиадная задача: Преобразования в таблице n×n — инварианты и принцип Дирихле

  Докажем, что в исходной таблице найдётся подтаблица 2×2, в которой стоит одна единица и три нуля.

  Найдется строка, в которой стоят одни нули (так как строк n, а единиц  n – 1).  Очевидно, что в таблице найдутся две соседние строки, в одной из которых стоят все нули, а в другой по крайней мере одна единица. В этой ненулевой строке найдутся две соседние клетки, в одной из которых стоит единица, а в другой – ноль. Эти две клетки и две соседние клетки из нулевой строки образуют искомую подтаблицу.

  Выберем в нашей таблице произвольную подтаблицу 2×2: пусть в ее левом верхнем углу стоит число a, в правом верхнем – b, в левом нижнем – c и в правом нижнем – d, а после проведения операции – a₁, b₁, c₁, d₁ соответственно. Рассмотрим выражения   D = (a + d) – (b + c)  и  D₁ = (a₁ + d₁) – (b₁ + c₁).   Возможны три случая.

  1) Выбранная клетка находится вне нашей подтаблицы, но лежит в строке или столбце, пересекающем нашу подтаблицу. Пусть для определенности она лежит в одной строке c a и b, тогда  a₁ = a + 1,  b₁ = b + 1,  c₁ = c,  d₁ = d  и  D₁ = (a + 1 + d) – (b + 1 + c) = D.

  2) Выбранная клетка находится вне нашей подтаблицы, и при этом она не лежит ни в строке, ни в столбце, пересекающем нашу таблицу. Тогда, очевидно, D₁ = D.

  3) Выбранная клетка находится внутри нашей подтаблицы. Пусть для определенности она – верхняя левая клетка подтаблицы, тогда  a₁ = a – 1,  b₁ = b + 1,  c₁ = c + 1,  d₁ = d  и  D₁ = D – 3.  (Если правая нижняя, то опять  D₁ = D – 3,  в противном случае  D₁ = D + 3.)

  Таким образом, мы показали, что остаток от деления D на 3 – инвариант. Однако в исходной таблице мы нашли подтаблицу 2×2, в которой  D = ±1,  а мы должны получить таблицу, в которой все числа равны, то есть с  D = 0,  что невозможно.

Нельзя.