TAOCP 7.2.1.4 Exercise 68
Let the perfect partition be a multiset with distinct values $v_1 < v_2 < \cdots < v_t$, where each value $v_i$ occurs with multiplicity $b_i-1 \ge 0$.
Section 7.2.1.4: Generating All Partitions
Exercise 68. [M23] [M23] What partition of n into m parts has the largest product a1 . . . am, when (a) m is given; (b) m is arbitrary?
Verified: no
Solve time: 5m46s
Solution
Let the perfect partition be a multiset with distinct values $v_1 < v_2 < \cdots < v_t$, where each value $v_i$ occurs with multiplicity $b_i-1 \ge 0$. A submultiset is determined by choosing integers $0 \le c_i \le b_i-1$, and its sum is $\sum_{i=1}^t c_i v_i$.
The number of distinct submultisets equals
$$ \prod_{i=1}^t b_i. $$
The hypothesis requires exactly $n+1$ submultisets, hence
$$ \prod_{i=1}^t b_i = n+1. \tag{1} $$
Each integer $0,1,\ldots,n$ must be representable by exactly one submultiset, since there are $n+1$ submultisets and $n+1$ target integers. Therefore the representation induced by the coefficients $c_i$ is a bijection between tuples $(c_1,\ldots,c_t)$ with $0 \le c_i \le b_i-1$ and integers in $[0,n]$. This forces a mixed-radix structure: choosing $v_1=1$ and
$$ v_{i+1} = b_1 b_2 \cdots b_i $$
makes all sums in the range $[0,n]$ achievable and distinct, and any perfect partition must be equivalent to such a system up to relabeling of values.
The number of elements in the multiset is
$$ k = \sum_{i=1}^t (b_i - 1) = \left(\sum_{i=1}^t b_i\right) - t. \tag{2} $$
The constraint (1) fixes the product of the integers $b_i \ge 1$. To minimize $k$, it suffices to minimize $\sum b_i - t$ under fixed product. Replace two factors $a,b \ge 1$ by a single factor $ab$. The change in the quantity $\sum (b_i-1)$ is
$$ (ab-1) - (a-1) - (b-1) = ab - a - b + 1 = (a-1)(b-1) \ge 0. $$
This transformation does not increase $k$ and strictly decreases it unless $a=1$ or $b=1$. Repeated application collapses all nontrivial factorizations to a single factor.
Thus the minimum occurs when
$$ t=1,\quad b_1 = n+1. $$
Then (2) gives
$$ k = (n+1) - 1 = n. $$
This case corresponds to a multiset with a single value repeated $n$ times, for example
$$ {1,1,\ldots,1}. $$
Its submultisets correspond uniquely to choosing $0,1,\ldots,n$ copies of $1$, producing sums $0,1,\ldots,n$ respectively, hence giving valid partitions of all integers in this range.
No construction with fewer than $n$ elements is possible, since any factorization with more than one nontrivial $b_i$ increases $\sum (b_i-1)$ by $(a-1)(b-1) > 0$ for at least one merge step.
Therefore the perfect partitions of $n$ with fewest elements are precisely the single-valued multisets repeated $n$ times, up to the choice of element value.
$$ \boxed{n} $$
This completes the proof. ∎