Putnam 2010, Problem A-1

Given a positive integer \( n \), what is the largest \( k \) such that the numbers \( 1, 2, \ldots, n \) can be put into \( k \) boxes so that the sum of the numbers in each box is the same? [When \( n = 8 \), the example \( \{1,2,3,6\}, \{4,8\}, \{5,7\} \) shows that the largest \( k \) is at least 3.]

Solution:
The largest such $k$ is $\left\lceil\frac{n+1}{2}\right\rceil = \left\lceil\frac{n}{2}\right\rceil$. For $n$ even, this value is achieved by the partition
$$\{1,n\},\{2,n-1\},\ldots;$$
for $n$ odd, it is achieved by the partition
$$\{n\},\{1,n-1\},\{2,n-2\},\ldots.$$

One way to see that this is optimal is to note that the common sum can never be less than $n$, since $n$ itself belongs to one of the boxes. This implies that $k \leq (1 + \cdots + n)/n = (n+1)/2$. Another argument is that if $k > (n+1)/2$, then there would have to be two boxes with one number each (by the pigeonhole principle), but such boxes could not have the same sum.

**Remark.** A much subtler question would be to find the smallest $k$ (as a function of $n$) for which no such arrangement exists.