Задача 67416
|
|
 |
Условие
Таблица 2×2024 заполнена целыми числами, причём в первой строке стоят числа из набора {1, ..., 2023}. Оказалось, что какие бы два столбца мы ни выбрали, разность их чисел из первой строки делится на разность их чисел из второй строки. Известно, что все числа во второй строке попарно различны. Обязательно ли тогда все числа в первой строке равны между собой?Решение
Лемма. Пусть $k$ и $l$ – натуральные числа, причём $\text{НОК}(k, l) < k + l$. Тогда $k + l$ делится на $k$ или на $l$.Доказательство. Пусть $d = \text{НОД}(k, l)$. По условию $kl < d(k + l)$, т.е. $(k – d)(l – d) < d^2$. Один из множителей меньше $d$ и делится на $d$, т.е. равен нулю. А $k + l$ делится на $d$. Лемма доказана.
Условие делимости не изменится, если все числа строки уменьшить на одно и то же целое число. Поэтому можно считать, что верхние числа находятся в пределах от 0 до 2022, а нижние – от 0 до $M$ (причём и 0, и $M$ присутствуют). Ясно, что $M$ > 2022. Разность чисел над 0 и $M$ делится на $M$, поэтому эти числа равны (пусть это число $b$).
Предположим, есть столбец вида $\binom{b+d}{k}$, где $d$ ≠ 0. Ясно, что $|d| \leqslant$ 2022. Сравнивая этот столбец со столбцами $\binom{b}{0}$ и $\binom{b}{M}$, видим, что $d$ делится как на $k$, так и на $M – k$. Поэтому $d$ делится на $\text{НОК}(k, M – k)$; по лемме $M$ делится на $k$ или на $M – k$. Как известно, у числа $M$ не более $2\sqrt{M}$ делителей, столько же дополнений этих делителей до $M$, значит, всего в верхней строке не более $4\sqrt{M}$ чисел, отличных от $b$. С другой стороны, и $k$, и $M – k$ не больше 2022, поэтому $M \leqslant$ 4044. Итак, в верхней строке не более $4\sqrt{4044}$ < 300 чисел, отличных от $b$. Зафиксируем один столбец вида $\binom{b+d}{k}$ и рассмотрим произвольный столбец вида $\binom{b}{k+q}$. По условию $d$ делится на $q$. Значит, в первой строке не более $4\sqrt{d} \leqslant 4\sqrt{2022}$ < 180 чисел $b$ ($q$ может быть как положительным, так и отрицательным). Но 300 + 180 < 2024. Противоречие.
