Dando una veloce occhiata alla dimostrazione di LB, mi pare molto simile alla mia. Il problema l\'ho preso da MathLinks, questa e\' la soluzione che ho postato (se vi interessa, <!-- BBCode Start --><I> <!-- BBCode Start --><A HREF="
http://www.mathlinks.ro/viewtopic.php?t=5939" TARGET="_blank">questo e\' il link</A><!-- BBCode End --></I><!-- BBCode End -->):
<BR>
<BR>For a given n, let\'s call k-sum any set of k distinct integers greater than 1 whose sum is n, and let\'s call isle any maximal set of consecutive integers in a k-sum. A hole is any gap between two consecutive isles of a k-sum, and a 1-hole is a hole consisting of just one element. Note that, for n>1, the problem is solved by a k-sum, because the product of a decomposition containing 1 can always be increased by adding 1 to its greatest element.
<BR>
<BR>1) Suppose we have a k-sum: if it has at least two holes, or a hole that is not a 1-hole, we can get a new k-sum with a greater product. Indeed, if b-a>1, then (a+1)(b-1)>ab. So, in a finite number of such steps, we get a k-sum with no holes, or with just a 1-hole.
<BR>
<BR>2) We note also that, if 2<=a<b, then ab>a+b. So, if the least element of our k-sum is m>=5, we can increase the product by taking the (k+1)-sum with 2, m-2 and the elements of the previous k-sum that are greater than m. Iterating steps 1) and 2) a finite number of times, we get a k-sum with no holes or just a 1-hole, and with least element <=4.
<BR>
<BR>3) Now, suppose that {h} is the only hole of our k-sum. Then, if the k-sum doesn\'t contain 2 and its last isle has at least 2 elements, we can get a (k+1)-sum with greater product, by taking 2, h and all the elements of our previous k-sum, except for h+2.
<BR>
<BR>4) If our k-sum contains 5 but not 2 and 3, construct a (k+1)-sum substituting 5 with 2 and 3.
<BR>
<BR>5) If we have the 2-sum {4, 6}, take the 3-sum {2, 3, 5} instead. Clearly, after a finite number of steps, we can\'t increase our product anymore by applying this and the above methods.
<BR>
<BR>Suppose the algorithm ends up with some k-sum. There are just a few possible patterns for its elements:
<BR>a) 2, 3, 4, ..., k+1;
<BR>b) 2, 3, 4, ..., h-1, h+1, ..., k+1, k+2 (with 3<=h<=k+1);
<BR>c) 3, 4, 5, ..., k+2;
<BR>d) 3, 4, 5, ..., k+1, k+3.
<BR>
<BR>We claim that the sums of the elements of the above k-sum\'s are pairwise distinct for every k and every pattern, so proving that the algorithm can end up with just one possible k-sum, no matter where it starts. It will follow that this is also the k-sum with maximal product: in fact, the algorithm increases the product of every non-terminal k-sum.
<BR>Indeed, this is true within the same k, because any k covers exactly k+2 consecutive integers. And finally, we see that the maximal sum for a given k (case d) is just equal to the minimal sum for k+1 (case a) minus 1.[addsig]