2014-06-07
Для заданного натурального значения $n \geq 3$ найти наибольшее возможное число возрастающих арифметических прогрессий, состоящих из трех членов, которые могут быть выбраны из какого-либо набора, содержащего ровно $n$ различных чисел.
Решение:
Рассмотрим число $a_{i}$ из набора $a_{1} < a_{2} < \cdots < a_{n}$. Количество трехчленных арифметических прогрессий, в которых это число является средним членом, не превосходит как $i -1$, так и $n – i$, поскольку на месте первого члена может стоять, только одно из чисел $a_{1}, \cdots, a_{i-1}$, а на месте последнего -одно из чисел $a_{i+1}, a_{i+2}, \cdots, a_{n}$. Поэтому общее число прогрессий не превосходит суммы
$\sum_{i =1}^{n} min \{ i -1, n – i \} = S$.
Если $n = 2l (l \in \mathbf{N} \ \{ l \} )$, то
$S = \sum_{i=1}^{l} (i - 1) + \sum_{i = l+1}^{n} (n-i) = l(l-1)$.
Если же $n = 2l + 1 (l \in \mathbf{N})$, то
$S = \sum_{i=1}^{l} (i - 1) + \sum_{i = l+1}^{n} (n-i) = l^{2}$.
Заметим, наконец, что полученные оценки для количества прогрессий достигаются в случае последовательности $a_{i}= i (i = 1, \cdots, n)$.