Задача 67519
|
|
 |
Условие
Пусть $A$ — набор из $n>1$ различных натуральных чисел. Для каждой пары чисел $a,b\in A$, где $a < b$, подсчитаем, сколько чисел в $A$ являются делителями числа $b-a$. Какое наибольшее значение может принимать сумма полученных $\frac{n(n-1)}2$ чисел?Решение
Сначала докажем оценку. Пусть $a_1 < a_2 < \ldots < a_n$ — элементы набора $A$.Заметим, что разность вида $a_j-a_i$ при $i < j$ может делиться на $a_k$ лишь при $k < j$.
Выберем любые $1\leq k < j \leq n$ и посмотрим, сколько из чисел вида $a_j-a_i$ (при $i < j$) может делиться на $a_k$. Все такие числа при $i\leq k$ отличаются менее, чем на $a_k$, поэтому на $a_k$ может делиться лишь одно из них. Значит, всего таких разностей может быть максимум $(j-k-1)+1=j-k$. Итого, получаем оценку $$ \sum_{1\leq k < j\leq n}(j-k)=\sum_{j=2}^n\frac{j(j-1)}2=\sum_{j=2}^n C_j^2=C_{n+1}^3 =\frac{(n+1)n(n-1)}6. $$ Это количество достигается, например, на наборе $1,2,2^2,\dots,2^{n-1}$. Здесь все неравенства из оценки обращаются в равенства, а значит, и оценка достигается.
Есть и другие примеры, в том числе, в которых все числа набора попарно взаимно простые, скажем, $a_1 = 1, a_2 = 2, a_3=3, a_4 = 7, \ldots , a_{k+1} = a_1a_2\ldots a_k+1$.
