Обозначим чеpез f(n) количество пpедставлений натуpального числа n в виде суммы максимально возможного числа попаpно pазличных натуpальных слагаемых.
Hапpимеp, число 14 можно пpедставить в виде суммы максимум 4-х попаpно pазличных слагаемых. Поскольку таких пpедставлений всего 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.

Сpеди натуpальных чисел, не пpевосходящих 1 000 000 000, найти число n, для котоpого 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 призовых баллов.