Работу выполнили ученицы 8 «А» класса МОУ СОШ 20 Им. Васлея Митты Научный руководитель Судеркина М.В. Задача о числах в таблице

Содержание работы: 1. Цели и задачи. 2. Введение. 3. Формулировка задачи. 4. Предварительные замечания. 5. Решение задачи для n=4. 6. Что дальше? 7. «Лемма» 8. Выводы.

Цели и задачи:

Введение:

Формулировка задачи: В таблице n x n произвольно расставлены числа 1, 2,..., n ². Доказать, что найдутся два соседних числа, разность между которыми не меньше n. Пояснение. Уточним термин «соседние числа». Мы называем два числа соседними, если клетки таблицы, в которых они стоят, имеют общую сторону.

Предварительные замечания: Легко расставить числа 1,..., n ² в таблице n x n так, чтобы разность любых двух соседних чисел не превосходила n. Примеры такой расстановки при n=5 приведены в таблицах 1 и

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

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

Существует много способов расставить числа 1,..., n² в таблице n x n так, чтобы максимальная разность между соседними числами равнялась n. Спрашивается, а нельзя ли расставить числа так, чтобы максимальная разность была меньше n? Оказывается, этого сделать нельзя именно это мы и собираемся доказать.

Решение задачи для n=4 Идею, на которой основано решение, особенно просто изложить при маленьких n. Возьмем таблицу 4x4, выберем в ней 4 клетки, в которых стоят числа 1, 2, 3 и 4. Поставим звездочки в те из оставшихся клеток таблицы, которые являются соседними для выбранных (таблица 3). 12* 3* ** *4

Заметим, что даже если выбранные клетки находятся на краю или в углу таблицы, то звездочек будет не меньше, чем четыре. Теперь, как бы мы не расставляли в таблице числа 5, 6,..., 16, в одну из клеток со звездочкой попадет число а 8 (поскольку звездочек минимум 4, а чисел, меньших 8, осталось всего три: 5, 6 и 7). Эта клетка является соседней по крайней мере для одной из клеток, в которых стоят числа 1,2, 3 и 4. 12* 3* ** *4

Итак, число а 8 соседствует с некоторым числом b 4. Тем самым a-b 4. Мы доказали, что при любом расположении чисел 1, 2, 3, 4,..., 16 в таблице 4x4 найдутся два соседних числа а и b таких, что a-b4.

Что дальше? Изложенное выше может привести к следующему поспешному выводу. Выберем в таблице n x n клетки, в которых стоят числа 1, 2,..., n. Поставим звездочки в те из оставшихся клеток, которые соседствуют с выбранными. Звездочек окажется минимум n. Поэтому, как ни ставить в таблицу числа n+1,..., n², найдется число а 2n, которое попадет в клетку со звездочкой и окажется соседним для некоторого числа bn. Разность чисел a-b, очевидно, n. В приведенном рассуждении имеется одна ошибка: неверно то утверждение, что напечатано курсивом и подчеркнуто. Неверно оно уже при n = 5: если мы расставим числа 1, …, 5 так, как это сделано в таблице 2, то звездочек будет только 4, а вовсе не 5. Оказывается, что положение можно исправить, надо лишь выбирать не n, а некоторое другое число клеток.

«Лемма» Пусть в таблице n x n расставлены числа 1,..., n². Тогда существует число т (1<т<n²), обладающее следующим свойством: если мы отметим клетки таблицы, в которых стоят числа 1,..., m, и поставим по звездочке в те из оставшихся клеток (содержащих числа m+1,..., n²), которые соседствуют с отмеченными, то звездочек в таблице окажется не менее чем n.

Доказательство Леммы: Пусть числа 1,..., n² как-то расставлены в таблице n x n. Обозначим через k наименьшее число, обладающее следующим свойством: в каждой строке и в каждом столбце имеется число, не превосходящее k (в таблицах 1, 2 и 4 число k равно соответственно 21, 15 и 9). Так как k наименьшее число, обладающее указанным свойством, то число k 1 этим свойством не обладает. Другими словами, найдется либо строка, либо столбец, не содержащие ни одного из чисел 1,..., k1. Рассмотрим три случая.

I случай. В каждом столбце имеется число, не превосходящее k1, но существует строка, не содержащая ни одного из чисел 1,..., k1. В этом случае положим m=k1 (например, m=20 в таблице 1 и m=8 в таблице 4)

Покажем, что m удовлетворяет требованиям леммы. Отметим клетки, содержащие числа 1,.,., m=k1, и поставим звездочки в те из оставшихся клеток, которые соседствуют с отмеченными (таблицы 5, 6). Каждый столбец содержит отмеченные клетки. Кроме того, в каждом столбце есть хоть одна неотмеченная клетка (так как целая строка не содержит отмеченных клеток). Поэтому в каждом столбце найдется хоть одна звездочка. Всего столбцов n; значит, и звездочек минимум n ***** **** 5* 7* *

II случай. В каждой строке имеется число, не превосходящее к 1, но существует столбец, не содержащий ни одного из чисел 1,...., к 1. Этот случай сводится к уже разобранному: достаточно отразить таблицу относительно главной диагонали (эта операция называется транспонированием; например, из таблицы 6 получается таблица 6*), тогда строки перейдут в столбцы, а столбцы в строки. Поэтому и здесь положим m=k * 2*** 4* 6* 8*

III случай 123* 45* 6** **8* *7 Существуют одна строка и один столбец, не содержащие чисел 1, …, k 1; число к стоит в центре «креста», образуемого этой строкой и этим столбцом (таблица 7). В этом случае положим m=k. Пусть число m=k стоит в клетке a lj на пересечении строки с номером I и столбца с номером j (в таблице 7 i=j=4). Отметим клетки, содержащие числа 1, …, m. Проверим, что в каждой строке имеются как отмеченные, так и неотмеченные клетки. Согласно определению числа k, в каждой строке имеется число, не превосходящее k. А так как m=k, то в каждой строке имеется отмеченная клетка. В i-й строке все клетки, кроме a lj, не отмечены. Наоборот, при l не равном i в l-той строке не отмечена a lj.

Итак, каждая строка содержит как отмеченные, так и неотмеченные клетки, а значит, содержит хоть одну звездочку. Следовательно, и в этом случае имеется минимум n звездочек. Так как случаи I, II и III исчерпывают все возможности, то лемма доказана.

Выводы: