Разделы 
Дополнительно
Задача по математике - 2002
2019-01-23 
Найдите наибольшее натуральное число $N$ такое, что для произвольной расстановки различных натуральных чисел от 1 до 400 в клетках квадратной таблицы $20 \times 20$ найдутся два числа, стоящих в одной строке или одном столбце, разность которых будет не меньше $N$.
Решение:
Приведем пример, показывающий, что $N = 209$. Разделим таблицу на два прямоугольника $20 \times 10$ по вертикали. В первом прямоугольнике расставим числа от 1 до 200 по строкам в возрастающем порядке (в первой строке - от 1 до 10, во второй - от 11 до 20 и т. д.). Во втором расставим так же числа от 201 до 400. Тогда максимальная разность между числами в любой строке равна 210 - 1 = 209, а в любом столбце 191 - 1 = 190. Поэтому $N < 209$.
Покажем, что $N = 209$ подходит. Рассмотрим два множества чисел: от 1 до 91 и от 300 до 400. Отметим все строки и столбцы, в которых есть числа первого множества, красным, а второго - синим. Покажем, что красным отмечено не менее 20 линий (т. е. строк или столбцов), а синим - не менее 21 (тогда какая-то линия будет отмечена и красным, и синим, и в ней максимальная разность чисел будет не меньше, чем 300 - 91 = 209, что и требовалось).
Пусть красным отмечено $i$ строк и $j$ столбцов. Тогда все первое множество находится в клетках их пересечения, поэтому $ij \geq 91$. Отсюда $i + j \geq 2\sqrt{ij} \geq 2\sqrt{91} > 19$. Аналогично, для второго множества сумма числа строк и столбцов $i + j \geq 2\sqrt{101} > 20$.
Ответ. 209.
Найдите наибольшее натуральное число $N$ такое, что для произвольной расстановки различных натуральных чисел от 1 до 400 в клетках квадратной таблицы $20 \times 20$ найдутся два числа, стоящих в одной строке или одном столбце, разность которых будет не меньше $N$.
Решение:
Приведем пример, показывающий, что $N = 209$. Разделим таблицу на два прямоугольника $20 \times 10$ по вертикали. В первом прямоугольнике расставим числа от 1 до 200 по строкам в возрастающем порядке (в первой строке - от 1 до 10, во второй - от 11 до 20 и т. д.). Во втором расставим так же числа от 201 до 400. Тогда максимальная разность между числами в любой строке равна 210 - 1 = 209, а в любом столбце 191 - 1 = 190. Поэтому $N < 209$.
Покажем, что $N = 209$ подходит. Рассмотрим два множества чисел: от 1 до 91 и от 300 до 400. Отметим все строки и столбцы, в которых есть числа первого множества, красным, а второго - синим. Покажем, что красным отмечено не менее 20 линий (т. е. строк или столбцов), а синим - не менее 21 (тогда какая-то линия будет отмечена и красным, и синим, и в ней максимальная разность чисел будет не меньше, чем 300 - 91 = 209, что и требовалось).
Пусть красным отмечено $i$ строк и $j$ столбцов. Тогда все первое множество находится в клетках их пересечения, поэтому $ij \geq 91$. Отсюда $i + j \geq 2\sqrt{ij} \geq 2\sqrt{91} > 19$. Аналогично, для второго множества сумма числа строк и столбцов $i + j \geq 2\sqrt{101} > 20$.
Ответ. 209.
