---

Показать решение

---

Скрыть решение

Решение

Мы решим общую задачу для таблицы n×n, причём получим для максимальной разности между соседними числами точную (неулучшаемую) оценку. В таблице n×n произвольно расставлены числа 1, 2,..., n². Доказать, что найдутся два соседних числа, разность между которыми не меньше n. Пояснение. Уточним термин ``соседние числа"". Мы называем два числа соседними, если клетки таблицы, в которых они стоят, имеют общую сторону. Легко расставить числа 1, 2, ..., n² в таблице n×n так, чтобы разность любых двух соседних не превосходила n. Примеры такой расстановки при n = 5 приведены в таблицах 1 и 2. Из таблицы 1 можно (меняя местами столбцы) получить ещё 119 = 5! - 1 таблиц, в которых разности между соседними числами не превосходят 5. Таблица 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

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

1	2	*
3	*
*			*
		*	4

Идею, на которой основано решение, особенно просто изложить при маленьких n. Возьмём таблицу 4×4, выберем в ней 4 клетки, в которых стоят числа 1, 2, 3 и 4. Поставим звёздочки в те из оставшихся клеток таблицы, которые являются соседними для выбранных (таблица 3). Заметим, что даже если выбранные клетки находятся на краю или в углу таблицы, то звёздочек будет не меньше, чем четыре (проверьте это самостоятельно). Теперь, как бы мы ни расставляли в таблице числа 5, 6, ..., 16, в одну из клеток со звёздочкой попадёт число а, большее или равное 8 (поскольку звёздочек минимум 4, а чисел, меньших 8, осталось всего три: 5, 6 и 7). Эта клетка является соседней по крайней мере для одной из клеток, в которых стоят числа 1, 2, 3 и 4. Итак, число а 8 соседствует с некоторым числом b 4. Тем самым a - b 4. Мы доказали, что при любом расположении чисел 1, 2, 3, 4,..., 16 в таблице 4×4 найдутся два соседних числа а и b таких, что а - b 4. Изложенное выше может привести к следующему поспешному выводу. Выберем в таблице n×n клетки, в которых стоят числа 1, 2, 3, 4,..., n. Поставим звёздочки в те из оставшихся клеток, которые соседствуют с выбранными. Звёздочек окажется минимум n. Поэтому, как ни ставить в таблицу числа n + 1, ..., n², найдётся число а 2n, которое попадёт в клетку со звёздочкой и окажется соседним для некоторого числа b n. Разность чисел а - b, очевидно, больше или равна n. В приведённом рассуждении имеется одна ошибка: неверно утверждение, напечатанное курсивом. Неверно оно уже при n = 5: если мы расставим числа 1,..., 5 так, как это сделано в таблице 2, то звёздочек будет только 4, а вовсе не 5. Оказывается, что положение можно исправить, надо лишь выбирать не n, а некоторое другое число клеток. Лемма. Пусть в таблице n×n расставлены числа 1, ..., n². Тогда существует число m (1 < m < n²), обладающее следующим свойством: если мы отметим клетки таблицы, в которых стоят числа 1,..., m, и поставим по звёздочке в те из оставшихся клеток (содержащих числа m + 1,..., n²), которые соседствуют с отмеченными, то звёздочек, в таблице окажется не менее чем n. Доказательство леммы. Пусть числа 1, ..., n² как-то расставлены в таблице n×n. Обозначим через k наименьшее число, обладающее следующим свойством: в каждой строке и в каждом столбце имеется число, не превосходящее k (в таблицах 1, 2 и 4 число k равно соответственно 21, 15 и 9). Так как k — наименьшее число, обладающее указанным свойством, то число k - 1 этим свойством не обладает. Другими словами, найдётся либо строка, либо столбец, не содержащие ни одного из чисел 1,..., k - 1. Рассмотрим три случая.
Таблица 4.

1	2	4	6	8
3
5
7
9

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

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	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. II с л у ч а й. В каждой строке имеется число, не превосходящее k - 1, но существует столбец, не содержащий ни одного из чисел 1,..., k - 1. Этот случай сводится к уже разобранному: достаточно отразить таблицу относительно главной диагонали (эта операция называется транспонированием; например, из таблицы 6 получается таблица 6"), тогда строки перейдут в столбцы, а столбцы — в строки. Таблица 6".

1	2	3	5	7
2	*	*	*
4	*
6	*
8	*

Поэтому и здесь положим m = k - 1. III случай. Существуют одна строка и один столбец, не содержащие чисел 1,..., k - 1; число k стоит в центре `` креста"", образуемого этой строкой и этим столбцом (таблица 7). В этом случае положим m = k. Пусть число m = k стоит в клетке a_ij на пересечении строки с номером i и столбца с номером j (в таблице 7 i = j = 4). Отметим клетки, содержащие числа 1,..., m. Проверим, что в каждой строке имеются как отмеченные, так и неотмеченные клетки. Согласно определению числа k, в каждой строке имеется число, не превосходящее k. А так как m = k, то в каждой строке имеется отмеченная клетка. В 1-й строке все клетки, кроме a_ij, не отмечены. Наоборот, при li в l-той строке не отмечена клетка а_lj. Итак, каждая строка содержит как отмеченные, так и неотмеченные клетки, а значит, содержит хоть одну звёздочку. Следовательно, и в этом случае имеется минимум n звёздочек. Так как случаи I, II и III исчерпывают все возможности, то лемма доказана. Таблица 7.

1	2	3	*
4	5	*
6	*		*
*		*	8	*
			*	7

Пусть в таблице n×n расставлены числа 1,..., n². Выберем в соответствии с леммой число m. Отметим клетки, содержащие 1,..., m, и поставим звёздочки в те из оставшихся клеток, которые соседствуют с отмеченными. По лемме звёздочек окажется не меньше чем n. Все числа в клетках со звёздочками больше m. Значит, наибольшее из них а m + n. Клетка, содержащая число а, соседствует с некоторой отмеченной клеткой, в которой стоит число b m. Так как a m + n, b m, то a - b n. Итак, мы указали два соседних числа а и b, разность между которыми больше или равна n. Тем самым наша задача полностью решена. (Статья ХХХ ``Задача о числах в таблице"", Квант 1971 номер 12 с.24-27.)