----
=====ММ4=====

**Конкурсная задача ММ4** (5 баллов)

Обозначим через f(n) количество представлений натурального числа n в виде суммы максимально возможного числа попарно различных натуральных слагаемых.
Например, число 14 можно представить в виде суммы максимум 4-х попарно различных слагаемых. Поскольку таких представлений всего 5 (14 = 1+2+3+8 = 1+2+4+7 = 1+2+5+6 = 1+3+4+6 = 2+3+4+5), заключаем f(14) = 5.

Среди натуральных чисел, не превосходящих 1 000 000 000, найти число n, для которого f(n) максимально.

**Решение**

Обозначим, число сочетаний из m по k через C(m,k).\\
Поскольку C(m,2) = 1+2+...(m-1), при n = C(m,2) f(n) = 1.\\
Когда n пробегает значения от C(m,2)+1 до C(m,2)+m-1, f(n) возрастает. Далее f снова принимает значение 1 (но в представлении n в виде суммы максимально возможного числа попарно различных натуральных чисел уже не m-1, а m слагаемых) и процесс повторяется для следующего биномиального коэффициента - C(m+1,2). Приведем начальный отрезок значений f (начиная с n=0), для наглядности расположив их в виде треугольника:\\
1\\
1 1\\
1 1 2\\
1 1 2 3\\
1 1 2 3 5\\
1 1 2 3 5 7\\
1 1 2 3 5 7 11\\
1 1 2 3 5 7 11 15\\
То, что каждая строка вплоть до последнего числа повторяет предыдущую, не случайно. В самом деле, можно установить биекцию между всеми представлениями числа C(m,2)+k в виде суммы m-1 попарно различных слагаемых и всеми представлениями числа C(m+1,2)+k в виде суммы m попарно различных слагаемых. Биективное соответствие задается вычитанием единицы из каждого слагаемого в представлении C(m+1,2)+k.\\
Поэтому для нахождения n, при котором f(n) принимает наибольшее значение на заданном отрезке натурального ряда, достаточно найти самое большое число вида C(m,2)-1, не превышающее 1000000000. Самое большое число вида C(m,2)-1, не превышающее 1000000000 это n = 999961559 (оно получается при m=44721).\\
Теоретически могло бы оказаться, что наибольшее значение повторилось бы для двух различных значений аргумента. Так было бы, если бы C(m+1)-2 равнялось 1000000000. Но, поскольку C(m+1,2)-2 превышает миллиард, найденное n - единственное.

**Обсуждение**

Предыдущие рассуждения показывают, что для нахождения значений f(n) для любого n достаточно научиться находить f(C(m,2)-1). Отметим (хотя для решения конкурсной задачи это и не важно), что f(C(m,2)-1) есть количество представлений числа m-1 в виде суммы натуральных слагаемых (в этом случае слагаемые не обязательно различны и их количество может меняться).

**Награды**

За полное правильное решение конкурсной задачи №4 Борис Бух получает 5 призовых баллов. 

----