Олимпиадная задача Новикова: максимальная сумма делителей разностей

Сначала докажем оценку. Пусть $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$.