Задача о числах в таблице

Квант 1971, №12 с. 24-26 Тег 551W

Задча о числах в таблице

М. Л. Гервер

В «Кванте» № 7 за 1971 год на странице 21 была сформирована следующая задача.

В квадратной таблице $6 \times 6$ произвольно рассматриены числа 1, 2, 3, …, 36. Доказать, что средние найдуемся два числа a и b, стояние в соседних клетках, также, что a—b $\geq 5$ .

Несколько лет тому назад аналогичная задача предлагалась на Московской математической олимпиде: доказать, что в таблице $9 \times 9$ , заполненной поларно разчислены числа, найдуется два соседних числа с разностью, больше или равной 6.

Ниже мы решим общую задачу для таблицы $n \times n$ , причем получим для максимальной разности между соседними числами точную (неулучшаемую) оценку.

Формулировка задачи

В таблице $n \times n$ произвольно рассматриены числа 1, 2, …, $n^2$ . Доказать, что найдуется два соседних числа, разность между которых не меньше n.

Пояснение. Уточним термин «соседние числа». Мы называем два числа соседними, если клетки таблицы, в которых они стоит, имеют общую сторону.

Предварительные замечания

Легко рассматриить числа 1, …, $n^2$ в таблице $n \times n$ так, чтобы разность любых двух соседних не превыс了她. Примеры такой рассстановки при $n=5$ приведены в таблице 1 и 2.

Из таблицы 1 можно (меня местами столбцы) получить еще 119 = 5!—1 таблиц, в которых разность соседними числами не пре-

Таблица 1.

1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

16 17 18 19 20

21 22 23 24 25

Таблица 2.

1 3 6 10 15

2 5 9 14 19

4 8 13 18 22

7 12 17 21 24

11 16 20 23 25

восходят 5. В таблице 2 можно, не увеличивая максимума разности между соседними числами, переставлять числа, стоящие дальше от диагонали, идущей излевого нижнего в правый верхний угол таблицы; например, можно поменять местами 1 и 2 или 23 и 24 и т. д. Совершенно аналогичные примеры строятся при любом n.

Существует много способов рассматривать числа 1,…, $n^2$ в таблице $n \times n$ так, чтобы максимальная разность между соседними числами равна n. Спрашивает, а нельзя ли рассматривать числа так, чтобы максимальная разность была меньше n?

Оказывается, этого сделать нельзя — именно это мы и собираемся доказать.

Решение задачи для $n=4$

Идею, на котором основано решение, особенно просто изложить при маленьких $n$ . Возьмем таблицу $4 \times 4$ , выберем в ней 4 клетки, в которых стоит числа 1, 2, 3 и 4. Поставим звездочки в те из оставшихся клеток таблицы, которые являются соседними для выбранных (таблица 3). Заметим, что даже если выбранные клетки находятся на краю или в углу таблицы, то звездочки будет не менше, чем четыре (проверьте это самостоятельно). Теперь, как бы мы ни расставли в таблице числа 5, 6, …, 16, в одну из клеток со звездочкой попадет число $a$ , больше или равное 8 (поскольку звездочек минимум 4, а чисел, меньших 8, осталось всего три: 5, 6 и 7). Эта клетка является соседней по крайней мере для одной из клеток, в которых стоит числа 1, 2, 3 и 4. Итак, число $a \geq 8$ соседует с некоторым числом $b \leq 4$ . Тем самым $a-b \geq 4$ .

Мы доказали, что при любом расположении чисел 1, 2, 3, 4, …, 16 в таблице $4 \times 4$ найдет два соседних числа $a$ и $b$ таких, что $a-b \geq 4$ .

Что дальше?

Изложенное выше может привести к следующему последному выводу.

Выберем в таблице $n \times n$ клетки, в которых стоит числа 1, 2, …, $n$ . Поставим звездочки в те из оставшихся клеток, которые соседуют с выбранными. Звездочек окажем最小им $n$ . Поэтому, как ни ставить в таблице числа $n+1$ , …, $n^2$ , найдется число $a \geq 2n$ , которое попадет в клетку со звездочкой и оказывается соседним для некоторого числа $b \leq n$ . Разность чисел $a-b$ , очевидно, больше или равна $n$ .

В приведенном рассуждении имеется одна ошибка: неверно утверждение, напечатанное курсивом. Неверно оно уже при $n=5$ : если мы расставим числа 1, …, $n^2$ . Тогда существует число $m$ ( $1 < m < n^2$ ), обладающее следующим свойством: если мы отметим клетки мыши, в которых стоящая на краю или в углу таблицы, то звездочек будет не менше, чем четыре (проверьте это самостоятельно). Теперь, как бы мы ни расставли в таблице числа 5, 6, …, 16, в одну из клеток со звездочкой попадет число $a$ , больше или равное 8 (поскольку звездочек минимум 4, а чисел, меньших 8, осталось всего три: 5, 6 и 7). Эта клетка является соседней по крайней мере для одной из клеток, в которых стоит числа 1, 2, 3 и 4. Итак, число $a \geq 8$ соседует с некоторым числом $b \leq 4$ . Тем самым $a-b \geq 4$ .

Лемма. Пусть в таблице $n \times n$ расставлены числа 1, …, $n^2$ . Тогда существует число $m$ ( $1 < m < n^2$ ), обладающее следующим свойством: если мы отметим клетки мыши, в которых стоящая на краю или в углу таблицы, то звездочек будет не менше, чем четыре (проверьте это самостоятельно). Теперь, как бы мы ни расставли в таблице числа 5, 6, …, 16, в одну из клеток со звездочкой попадет число $a$ , больше или равное 8 (поскольку звездочек минимум 4, а чисел, меньших 8, осталось всего три: 5, 6 и 7). Эта клетка является相邻 в таблице числа 1, …, $n^2$ , найдется число $a \geq 2n$ , которое попадет в клетку со звездочкой и оказывается соседним для некоторого числа $b \leq n$ . Разность чисел $a-b$ , очевидно, больше или равна $n$ .

1 случай. В каждом столбце имеется число, не превысаящее $k-1$ , но существует строка, не содержащая ни одного из чисел 1, …, $k-1$ .

Таблица 5.

| 1 | 2 | 3 | 4 | 5 |
| :—: | :—: | :—: | :—: | :—: |
| 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 |
| 16 | 17 | 81 | 19 | 20 |

Таблица 6.

| 1 | 2 | 4 | 6 | 8 |
| :—: | :—: | :—: | :—: | :—: |
| 3 | * | * | * | * |
| 5 | * | | | |
| 7 | * | | | |

В этом случае положим $m=k-1$ (например, $m=20$ в таблице 1 и $m=8$ в таблице 4).

Покажем, что $m$ удовлетворяет требованиям леммы.

Отметим клетки, содержащие числа 1, …, $m=k-1$ , и поставим звездочки в те из оставшихся клеток, которые соседствуют с отмеченными (таблицы 5, 6).

Каждай столбец содержит отмечные клетки. Кроме того, в каждом столбце есть хотя одна неотмеченная клетка (так как целая строка не содержит отмечных клеток). Поэтому в каждом столбце найдется хотя одна звездочка. Все столбцов $n$ ; значит, и звездочка — минимум $n$ .

П слуай. В каждой строке имеется число, не превысывающее $k-1$ , но существует строки, не содержащий ни одного из чисел 1, …, $k-1$ .

Этот случай совпит к уже разобранному: достаточно отразить таблицу относительно главной диагонали (эта операция называется распись).