Число 15 можно тремя способами разложить в сумму трёх натуральных чисел так, что все 9 чисел различны:
$$15=1+6+8=2+4+9=3+5+7.$$
Для каждого натурального $n$ обозначим через $k(n)$ наибольшее число троек натуральных чисел, дающих в сумме $n$ и состоящих из $3k(n)$ различных чисел. Докажите, что
а) Пусть $p=p(n)$ — наибольшее целое число, меньшее $\dfrac{n+1}6$. Тогда $p\gt\dfrac{n}6-1$ (поскольку между $\dfrac{n}6-1$ и $\dfrac{n}6+\dfrac16$ обязательно есть целое число), и $p$ троек, указанные на полях, удовлетворяют условию задачи. Таким образом, $k(n)\ge p(n)\gt\dfrac{n}6-1$.
б) Пусть имеется $k$ троек различных натуральных чисел, в сумме дающих $n$. Обозначим через $s$ сумму всех $3k$ чисел, входящих в эти тройки. Тогда, с одной стороны, $s=nk$, а с другой стороны, $s\ge1+2+\ldots+3k=\dfrac{3k(3k+1)}2$. Поэтому $nk\ge\dfrac{3k(3k+1)}2$, откуда $k\le\dfrac{2n-3}9$. Таким образом, $k(n)\le\dfrac{2n-3}9\lt\dfrac{2n}9$.
в) По доказанному в пункте б) $k(100)\le\left[\dfrac{2\cdot100-3}9\right]=21$. Далее, $p(100)=16$, так что согласно а) мы можем указать 16 троек:
$(1,47,52)$, $(2,45,53)$, $\ldots$, $(16,17,67)$.
При этом остались неиспользованными числа 18, 20, 22, $\ldots$, 48, 50. Из этих чисел нам надо выбрать ещё пять троек, в сумме дающих 100. Для этого из каждого из этих чисел вычтем 16 и полученные числа разделим пополам. Мы придём к набору чисел 1, 2, $\ldots$, 17; из них надо выбрать пять троек с суммой $\dfrac{100-3\cdot16}2=26$. Так как $p(26)=4$, четыре тройки мы получаем сразу: $(1,11,14)$, $(2,9,15)$, $(3,7,16)$, $(4,5,17)$. Остались числа 6, 8, 10, 12, и из них надо выбрать три с суммой 26. Это сделать легко: $6+8+12=26$.
Теперь, удвоив числа и добавив к ним по 16, мы получим последние 5 троек с суммой 100; они приведены на полях.
г) По неравенству б) $k(500)\le110$. Немного видоизменив тройки, указанные в пункте а), получим первые $p(500)=83$ тройки: $(1,249,250)$, $(2,247,251)$, $\ldots$, $(83,85,332)$. Остались неиспользованными числа 84, 86, $\ldots$, 248. От этого набора чисел линейным преобразованием $x\to\dfrac x2-41$ переходим к набору 1, 2, $\ldots$, 83, из которого надо выбрать 27 троек с суммой 127. Сразу же выбираем $p(127)=21$ тройку: $(1,62,64)$, $(2,60,65)$, $\ldots$, $(21,22,84)$. Остались числа 23, 25, $\ldots$, 63. От них преобразованием $x\to\dfrac{x-21}2$ переходим к набору 1, 2, $\ldots$, 21, из которого надо выбрать 6 троек с суммой 32. А это сделать легко: $(1,15,16)$, $(2,13,16)$, $(3,11,18)$, $(4,9,19)$, $(5,7,20)$, $(6,12,14)$.
В общем случае подобное рассуждение приводит к результату: $\dfrac29n-\dfrac{11}6\log_4\dfrac n3\le k(n)\le\dfrac{2n-3}9$ (при $n\ge6$).
