Partitions with maximal products

Consider all the ways that we can write an integer 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₁ + ... + a_k-1 + a_k + 1, then this corresponds to the product a₁...a_k; clearly we can rewrite n as
n = a₁ + ... + a_k-1 + (a_k + 1)
(where we've combined a_k and 1 into a single part), and
a₁a₂...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 3n has n parts equal to 3, and has product 3 × 3^n-1;
- the maximal product of a partition of 3n+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 3n+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 3n+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).