Putnam 2010 A1

Given a positive integer $n$, what is the largest $k$ such that the numbers $1,2,...,n$ can be put into $k$ boxes so that the sum of the numbers in each box is the same?

Putnam 2010 A1

Hint: I think it’s enough to see that $n$ must be in one of the boxes, and to make $k$ big, the sum in the boxes must be small. Therefore divide into two cases, for $n$ odd and even, and the rest is easy.