Задача №17180

На доске написано несколько различных натуральных чисел. Известно, что для любых двух различных чисел $a$ и $b$ из этого набора их сумма $a+b$ делится на модуль их разности $|a-b|\text{.}$ Пусть $S$ — сумма всех написанных на доске чисел.
А) Может ли на доске быть ровно $3$ числа?
Б) Может ли на доске быть ровно $100$ чисел?
В) Найдите наименьшее значение $S\text{,}$ если на доске написано $4$ числа.

Лемма. Если $x<y$ — натуральные, то условие $(y-x)\mid (x+y)$ равносильно $(y-x)\mid 2x\text{.}$

Доказательство. $x+y=2x+(y-x)\text{,}$ поэтому $(y-x)\mid (x+y)\iff (y-x)\mid 2x\text{.}$

А) Да, можно. Пример: $\{1,2,3\}\text{.}$

Проверка: $|2-1|=1\mid 3$ ✓; $|3-1|=2\mid 4$ ✓; $|3-2|=1\mid 5$ ✓.

Б) Да, можно.

Конструкция. Если набор $A=\{a_1,a_2,\dots ,a_n\}$ удовлетворяет условию, то набор

где $L=\mathrm{lcm}(a_1,\dots ,a_n)\text{,}$ — также удовлетворяет условию и содержит $n+1$ элементов.

Проверка. Пары двух типов:

• $(L,L+a_i)\text{:}$ разность $a_i\text{,}$ сумма $2L+a_i\text{.}$ Условие $a_i\mid 2L+a_i$ равносильно $a_i\mid 2L\text{.}$ Так как $a_i\mid L\text{,}$ имеем $a_i\mid 2L\text{.}$ ✓
• $(L+a_i,L+a_j)\text{,}$ $i\ne j\text{:}$ разность $|a_i-a_j|=d\text{,}$ сумма $2L+a_i+a_j\text{.}$ Из условия для $A\text{:}$ $d\mid (a_i+a_j)\text{.}$ Также $d\mid 2a_i$ (по лемме применённой к паре $(a_i,a_j)\subset A\text{,}$ причём $a_i=\min$); и так как $a_i\mid L\text{,}$ то $2L=(L/a_i)\cdot 2a_i$ кратно $d\text{.}$ Значит $d\mid 2L+(a_i+a_j)\text{.}$ ✓

Итерируя от стартового набора $\{1,2,3\}$ ($n=3$) ровно $97$ раз, получаем подходящий набор из $100$ чисел. Например, первый шаг даёт $\{6,7,8,9\}$ (проверка: $|9-6|=3\mid 15$ ✓, и т. д.).

В) Минимум $S$ при $4$ числах.

Пусть $m$ — наименьшее число набора. По лемме, для любого $a$ из набора с $a>m\text{:}$ $a-m\mid 2m\text{,}$ то есть $a-m$ — делитель числа $2m\text{.}$

Значит остальные три числа имеют вид $m+d\text{,}$ где $d\mid 2m\text{.}$

• $m=1\text{:}$ $2m=2\text{,}$ делители $\{1,2\}\text{.}$ Возможные числа: $1+1=2\text{,}$ $1+2=3\text{.}$ Получаем максимум $3$ числа: $\{1,2,3\}\text{.}$ Для $4$ чисел не подходит.
• $m=2\text{:}$ $2m=4\text{,}$ делители $\{1,2,4\}\text{.}$ Возможные числа: $3,4,6\text{.}$ Единственный кандидат на $4$ числа: $\{2,3,4,6\}\text{.}$
  Проверка всех $6$ пар: $|3-2|=1\mid 5$ ✓; $|4-2|=2\mid 6$ ✓; $|6-2|=4\mid 8$ ✓; $|4-3|=1\mid 7$ ✓; $|6-3|=3\mid 9$ ✓; $|6-4|=2\mid 10$ ✓.
  Все условия выполнены. $S=2+3+4+6=15\text{.}$
• $m⩾3\text{:}$ сумма любых $4$ различных натуральных чисел $⩾m+(m+1)+(m+2)+(m+3)=4m+6⩾18>15\text{.}$

Таким образом, минимум $S=15$ достигается на наборе $\{2,3,4,6\}\text{.}$

Ответ:

А) Да

Б) Да

В) $S=15$