Putnam 2010: Day 1

I took the first part of the Putnam 2010 exam yesterday, it did not go well. I actually liked most of the problems that day, and probably could have gotten three of them. I'm pretty sure I solved only one. (I'm trying to check a solution for a second problem at the moment). For most of the other problems I attempted, I was starting on some incorrect premise, which kind of threw me off. I guess what I should take away from this is that I need to be more careful.

So, here is the problem I did solve, it's actually really easy, and didn't take very long:


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?
[When n = 8, the example {1,2,3,6},{4,8},{5,7}
shows that the largest k is at least 3.]

The answer is floor((n+1)/2) (floor(x) denotes the greatest integer smaller than x).
The reasoning is as follows:
If you have a k larger than that, you must have at least 2 boxes with a single number in them, since all the numbers are distinct, then the sums of the numbers in those two boxes are different. (To see this, if only one box has a single number, and each other box has at least two numbers, you get a total number of numbers larger than n).


To show that it's achievable, note that if n is even floor((n+1)/2)
=n/2. So we can just pair the numbers: (1,n), (2,n-1)..., so they all have sum n+1, and put one pair in each box.
With n odd, floor((n+1)/2) becomes (n+1)/2. So we can have one box with just (n), along with the pairs (1,n-1) (2,n-2), etc, all of which sum to n.