Разбить число не слагаемые

[Stotch]

Помогите плз решить в общем виде задачу:
Разбить натуральное число $N$ на $k$ РАЗНЫЕ,ЦЕЛЫЕ слагаемые $N_i$ таким образом чтобы их произведение было максимальным, т. е найти все $N_i, i=1,...,k$ такие что

$$ \prod\limits_{i=1}^k N_i \to \max$$

,при

$$\sum\limits_{i=1}^k N_i=N $$

Подойдет любое решение можно даже на нескольких примеров,главное объяснить,когда я решал задачу разбиения на $k$ слагаемых любых(т.е которые могут повторятся) то пришел к выводу что чем больше слагаемых тем лучше и что эти слагаемые должны состоять из 2-ек и 3-ек,а как быть тут?

[nikvic]

Stotch в сообщении #667955 писал(а):

пришел к выводу что чем больше слагаемых тем лучше и что эти слагаемые должны сосотоять из 2-ек и 3-ек,а как быть тут?

По условию, каждое слагаемое - не более одного раза
Так что двигатся дальше. К четвёркам, пятёркам...

[Stotch]

Т.е нужно сначала разложить число на 2 и 3?а потом складывать эти двойки и тройки чтобы получались разные числа и чтобы их было как можно больше?я еще не совсем понимаю как определить сколько должно быть 2-ек и троек? в случае когда числа могут быть любые

[Shadow]

Stotch в сообщении #667987 писал(а):

я еще не совсем понимаю как определить сколько должно быть 2-ек и троек? в случае когда числа могут быть любые

Как Вы думаете, наличие трех двоек оправдано? Нельзя ли их заменить на что-то более выгодное? Но здесь совсем другая задача.

Stotch в сообщении #667955 писал(а):

чем больше слагаемых тем лучше

Согласен. Но не единички, конечно. Т.е $2+3+4+\cdots$ Пока сумма не станет больше либо равна нашему числу. А если больше, то..

[Stotch]

вот сижу и пришел к выводу что троек должно быть больше,но в каком соотношении?
а вот когда мы на разные слагаемые раслкадываем что делать когда сумма становится больше нашего числа?
вот например 17=2+3+4+5+x что вместо x должно быть?тройку нельзя,нужно что то делать с 4 и 5?но что?и как это определить и доказать?

[arseniiv]

Добавляйте теперь единицы к имеющимся слагаемым.

[nikvic]

Stotch в сообщении #667987 писал(а):

еще не совсем понимаю как определить сколько должно быть 2-ек и троек?

А слово РАЗНЫЕ в условии понимаете?

[Stotch]

я говорил про двойки и тройки в задачи когда числа могут быть любые,так в ткой задачи определить количество двоек и троек?т.е я правильно понимаю что 17=2+4+5+6 и эти числа дадут максимальное произведение?а какой общий алгоритм?

[Deggial]

Stotch, формулы на форуме следует записывать ТеХом. Инструкции здесь или здесь (или в этом видеоролике).

[arseniiv]

Stotch в сообщении #668191 писал(а):

т.е я правильно понимаю что 17=2+4+5+6 и эти числа дадут максимальное произведение?

Для 17 — да.

Возможно, алгоритм можно увидеть, рассмотрев другие, кроме 17, числа.

[VAL]

arseniiv в сообщении #668431 писал(а):

Возможно, алгоритм можно увидеть, рассмотрев другие, кроме 17, числа.

Похоже, алгоритм будет в точности такой же, как для 17.
Пусть наше $n$ равно $s+k$, где $s=2+3+\dots+j$ и $k\le j$. Тогда искомое представление $2+3+\dots+(j-k)+(j-k+2)+(j-k+3)+\dots+(s+1)$

[arseniiv]

Иногда лучшее представление начинается с 3. Например, $34 = 3 + 4 + 5 + 6 + 7 + 9$. Вот факты для чисел до 50:

\begin{array}{ccc} \text{Число} & & \text{Слагаемые} \\ 1 & \to & 1 \\ 2 & \to & 2 \\ 3 & \to & 3 \\ 4 & \to & 4 \\ 5 & \to & 3, 2 \\ 6 & \to & 4, 2 \\ 7 & \to & 4, 3 \\ 8 & \to & 5, 3 \\ 9 & \to & 4, 3, 2 \\ 10 & \to & 5, 3, 2 \\ 11 & \to & 5, 4, 2 \\ 12 & \to & 5, 4, 3 \\ 13 & \to & 6, 4, 3 \\ 14 & \to & 5, 4, 3, 2 \\ 15 & \to & 6, 4, 3, 2 \\ 16 & \to & 6, 5, 3, 2 \\ 17 & \to & 6, 5, 4, 2 \\ 18 & \to & 6, 5, 4, 3 \\ 19 & \to & 7, 5, 4, 3 \\ 20 & \to & 6, 5, 4, 3, 2 \\ 21 & \to & 7, 5, 4, 3, 2 \\ 22 & \to & 7, 6, 4, 3, 2 \\ 23 & \to & 7, 6, 5, 3, 2 \\ 24 & \to & 7, 6, 5, 4, 2 \\ 25 & \to & 7, 6, 5, 4, 3 \\ 26 & \to & 8, 6, 5, 4, 3 \\ 27 & \to & 7, 6, 5, 4, 3, 2 \\ 28 & \to & 8, 6, 5, 4, 3, 2 \\ 29 & \to & 8, 7, 5, 4, 3, 2 \end{array}

\begin{array}{ccc} \text{Число} & & \text{Слагаемые} \\ 30 & \to & 8, 7, 6, 4, 3, 2 \\ 31 & \to & 8, 7, 6, 5, 3, 2 \\ 32 & \to & 8, 7, 6, 5, 4, 2 \\ 33 & \to & 8, 7, 6, 5, 4, 3 \\ 34 & \to & 9, 7, 6, 5, 4, 3 \\ 35 & \to & 8, 7, 6, 5, 4, 3, 2 \\ 36 & \to & 9, 7, 6, 5, 4, 3, 2 \\ 37 & \to & 9, 8, 6, 5, 4, 3, 2 \\ 38 & \to & 9, 8, 7, 5, 4, 3, 2 \\ 39 & \to & 9, 8, 7, 6, 4, 3, 2 \\ 40 & \to & 9, 8, 7, 6, 5, 3, 2 \\ 41 & \to & 9, 8, 7, 6, 5, 4, 2 \\ 42 & \to & 9, 8, 7, 6, 5, 4, 3 \\ 43 & \to & 10, 8, 7, 6, 5, 4, 3 \\ 44 & \to & 9, 8, 7, 6, 5, 4, 3, 2 \\ 45 & \to & 10, 8, 7, 6, 5, 4, 3, 2 \\ 46 & \to & 10, 9, 7, 6, 5, 4, 3, 2 \\ 47 & \to & 10, 9, 8, 6, 5, 4, 3, 2 \\ 48 & \to & 10, 9, 8, 7, 5, 4, 3, 2 \\ 49 & \to & 10, 9, 8, 7, 6, 4, 3, 2 \\ 50 & \to & 10, 9, 8, 7, 6, 5, 3, 2 \end{array}

Алгоритм видится такой: заполняем слагаемые числами $2,3,4,\ldots$, пока возможно, а потом прибавляем к ним единицы, идя от большего слагаемого к меньшему. Если единицы не кончились за первый проход, делаем ещё один. Остаётся только доказать, что он верный.

-- Пн янв 07, 2013 20:17:17 --

(Прошу простить за обратный порядок слагаемых. Надеюсь, он не мешает.)

[Shadow]

Shadow в сообщении #668009 писал(а):

$2+3+4+\cdots$ Пока сумма не станет больше либо равна нашему числу. А если больше, то..

убираем избыточное число. Если избыточное 1, убираем двойку и увеличиваем наибольшее на 1. Результат такой же, как у arseniiv,VAL. А вот совсем строгое доказательство не получается у меня. Слишком много "очевидно, что "

[VAL]

arseniiv в сообщении #668466 писал(а):

Иногда лучшее представление начинается с 3.

Разумеется.

Цитата:

Если единицы не кончились за первый проход, делаем ещё один.

Угу.
Этот случай я прозевал (забыл, что слагаемые с двойки идут).
Он возникает в точности для чисел на 2 меньших треугольных.

[arseniiv]

Кстати, в задаче число слагаемых ровно заданное $k$. А мы, если не ошибаюсь, решали задачу для всех разбиений…

Если $k = 2$, то лучше чем на почти равные половины ($n \mapsto (\lfloor \frac{n-1}2 \rfloor, \lfloor \frac n2 \rfloor + 1)$) не разбить, но это и так понятно.

(Оказывается, всё просто, хотя установил это не я. Впрочем, мой алгоритм всё равно остаётся применим, если не ошибаюсь.)