Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание


ММ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 призовых баллов.


 

 


Страница: [[marathon:problem_4]]

marathon/problem_4.txt · Последние изменения: 2015/10/03 23:36 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006