*n*as a

*sum*of nonnegative integers. Then for each of these sums take the

*product*of the summands. What is the largest such product?

For example, we can write

6 = 5+1 = 4+2 = 4+1+1 = 3+3 = 3+2+1 = 3+1+1+1 = 2+2+2 = 2+2+1+1 = 2+1+1+1+1 = 1+1+1+1+1+1

and the corresponding products are

6, 5, 8, 4, 9, 6, 3, 8, 4, 2, 1

of which 9 = 3 × 3 is the largest.

First, any partition of

*n*(that's what these sums are called) which includes a 1 does

*not*give rise to the maximal product. If we have n = a

_{1}+ ... + a

_{k-1}+ a

_{k}+ 1, then this corresponds to the product a

_{1}...a

_{k}; clearly we can rewrite n as

n = a

_{1}+ ... + a

_{k-1}+ (a

_{k}+ 1)

(where we've combined a

_{k}and 1 into a single part), and

a

_{1}a

_{2}...a

_{k-1}(a

_{k}+1)

is larger.

Similarly, any partition of

*n*which contains a part which is 5 or larger can't give rise to the maximal product. Simply replace a part k ≥ 5 by (k-3)+3.

So any partition of

*n*having maximal product has all its parts equal to 2, 3, or 4. Furthermore, we can break a part equal to 4 into two parts equal to 2 without changing the product; for example 4+3 and 3+2+2 both give the product 12. So if we just care about the value of the maximal product, it's enough to consider parts equal to 2 or 3.

Finally, any partition containing three or more parts equal to 2 doesn't have maximal product; we can replace 2+2+2 with 3+3 and increase the product. For example, 3+2+2+2+2 is

*not*the partition of 11 having maximal product (it has product 48) since we can replace three of the parts equal to 2 with two parts equal to 3, giving 3+3+3+2, which has product 54.

So the maximal product of a partition of

*n*must be given by a partition which has all parts equal to 3, except for zero, one, or two parts equal to 2. Furthermore, considering

*n*modulo 3 tells us that only one of these three situations is possible. Thus, we see that:

- the maximal product of a partition of 3

*n*has

*n*parts equal to 3, and has product 3 × 3

^{n-1};

- the maximal product of a partition of 3

*n*+1 has

*n-1*parts equal to 3 and two parts equal to 2, and has product 4 × 3

^{n-1};

- the maximal product of a partition of 3

*n*+2 has

*n*parts equal to 3 and one part equal to 2, and has product 6 × 3

^{n-1}.

For example, the partition of 12 having maximal product is 3+3+3+3, with product 81; the partition of 13 having maximal product is 3+3+3+2+2, with product 108; the partition of 14 having maximal product is 3+3+3+3+2, with product 162. These are unique, except that in the 3

*n*+1 case we can replace the two 2s with one 4.

The sequence generated in this way is in the Encyclopedia of Integer Sequences; although I invented the problem myself, it's (unsurprisingly) well-known in problem-solving circles. For example, it was 1979 Putnam exam problem A1 (in the special case n = 1979)

*and*1976 IMO problem B1 (in the special case n = 1976).

## 3 comments:

This function of n comes up in a theorem of Moon and Moser, "On cliques in graphs", Israel J. Math, 1965. They show that an n-vertex graph has at most this many distinct cliques. The examples of graphs that match this bound are formed by starting from a complete graph, partitioning it in this way, and removing the edges within each partition, and their cliques are formed by choosing one vertex per set in the partition.

I think you must have made an error, counter example: n = 1

:)

This was the first problem on the first Putnam test I ever took, way back in 1979 (as you point out). And yes, it was my first completed problem as well!

Post a Comment