HOME

On maximising a product

Show original manuscript
E.W. Dijkstra Archive: On maximising a product (EWD 856)

On maximising a product

The problem is to construct a set of positive integers with given sum such that their product is as large as possible.

The first observation is that we need not include integers 4. The reason is that such an integer k can be replaced, without changing the sum, by the two integers 2 and k-2, thereby replacing in the product a factor k by a factor 2k - 4 and that we don't lose if 2k - 4 k, i.e. if k 4.

The second observation is that 1 only needs to be included if it is the only integer in the set, i.e. if the given sum equals 1. In all other cases we can increase the product without changing the sum by removing the 1 (which does not contribute to the product) and increasing one of the other integers by 1.

In the general case this leaves us with a set of 2's and 3's. The final observation is that we don't need to include 3 or more 2's: 2+2+2 = 3+3 but 222 < 33.

*                *
*

We solved this problem a number of years ago (and were not the first to do so), but in my memory the argument was less clean than above. It was more or less polluted by

the circumstance that the answer is not unique if the given sum is of the form 3n + 4: two 2's may be replaced by one 4.

Another way of complicating the first observation is to treat even and odd values separately, e.g. comparing for k = 2x the value 2x with x2, and for k = 2x + 1 the value 2x + 1 with x(x + 1).


California Institute of Technology
PASADENA, CA 91125
United States of America
14 June 1983
prof.dr. Edsger W. Dijkstra
Burroughs Research Fellow

Transcriber: Kevin Hely.
Last revised on Sat, 20 Sep 2003.