School starts soon at my alma mater, WWU. For me, Fall quarter always meant I would be taking the Putnam Exam, regarded as one of the most difficult (or the most difficult) math competitions for undergraduates. It consists of two three-hour sessions with six problems each. Most years, the median score on the exam is zero out of 120 points.
The first year I sat the exam, in 2010, this was one of the problems:
There are 2010 boxes labeled \(B_{1}, B_{2}, \ldots, B_{2010}\) and \(2010n\) balls have been distributed among them, for some positive integer \(n\). You may redistribute the balls by a sequence of moves, each of which consists of choosing an \(i\) and moving exactly \(i\) balls from box \(B_i\) into any one other box. For which values of \(n\) is it possible to reach the distribution with exactly \(n\) balls in each box, regardless of the initial distribution of balls?
Break it down
Whew, what a mouthful! Let’s break that into pieces.
There are 2010 boxes labeled \(B_{1}, B_{2}, \ldots, B_{2010}\)
So far, so good.
… and \(2010n\) balls have been distributed among them, for some positive integer \(n\).
Okay, so if \(n\) is 2, for example, there are 4020 balls. And all the balls are in some box or other.
You may redistribute the balls by a sequence of moves,
That sounds good to me. What are the moves?
each of which consists of choosing an \(i\) and moving exactly \(i\) balls from box \(B_i\) into any one other box.
So I could take 3 balls out of box \(B_3\) and put them in box \(B_5\). But if I wanted to take balls out of box \(B_5\), I’d have to take them out 5 at a time. And I can do this as many times as I want.
For which values of \(n\) is it possible to reach the distribution with exactly \(n\) balls in each box,
We’re looking to divide the \(2010n\) balls evenly among all the boxes, but maybe it doesn’t work for every \(n\)?
regardless of the initial distribution of balls?
Okay, so my worst enemy could be stacking the deck against me, setting things up so in the worst way they know how, and I still have to be able to evenly distribute the balls.
A smaller version of the same problem
It’s a little hard to visualize 2010 boxes, so lets go with something smaller. How about five? Play with the demo below for a bit. You can move \(i\) balls from box \(B_i\) by dragging them to another box. Can you get all of the balls distributed evenly? If so, try making it harder by lowering the ‘Ball Multiplier’ (that’s the \(n\) from the \(5n\) balls we’re working with).
If you played that for a bit, you probably developed some sort of strategy. (If you didn’t, go ahead; we’ll wait).
Rescue missions
For me, a strategy that seems to work is to move balls towards box \(B_1\), and redistribute from there one at a time. We can also use the balls in box \(B_1\) to ‘rescue’ balls in another box. This is most easily understood with an example.
In the game above, our \(n\) is 1, so we’re trying to get 1 ball in each box. Box \(B_3\), with two balls, has too many! We need to take one out, but the rules are that we have to take out 3 at a time. So, we will send a ball to ‘rescue’ the balls in \(B_3\).
Okay, so everything’s peachy then, right? Not so fast. Are we always going to be able to execute a rescue mission like that? What could go wrong? I’ll leave you to contemplate that while I admire this orange.
A wrench in the works
What if everyone needs a rescue, and no one is there to help? Box \(B_1\) has 0 balls, \(B_2\) has fewer than 2, \(B_3\) has fewer than 3, and so on.
What can we do about this? Well, we could make sure that there are so many balls that this never happens. For this, it is helpful to think of a worst-case scenario. In the very worst case, with the most stuck balls, every box \(B_i\) has \( i -1\) balls. There is no slack anywhere in the system.
In the 5 boxes case, the worst-case scenario involves 10 balls: \( 0 + 1 + 2 + 3 + 4\). We know that if the game comes to us in that state, we’ll never get the balls evenly distributed. But if there’s even one more ball, everything frees up. Wherever that extra ball lands, we can move the balls in that box into \(B_1\), and from there execute rescue missions.
How many balls do we need for 2010 boxes? We still need one more than worst case of \(0 + 1 + 2 + 3 + \ldots + 2009 \), but what is that sum? It turns out there’s an easy way to count up all the numbers from 1 to 2009 (or really anything you like).
How to count
Again, let’s work with a smaller version of the problem. Let’s add up the numbers from 1 to 10.
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
Now, add another row below it, but reversed.
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1
Each column sums to 11!
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1
-----------------------------------------------
11 + 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11
Since there are 10 columns, we have \(11 \cdot 10\). But we needed two rows of \( 1 + 2 + \ldots + 10\) to get to that, so we have to cut our \(11 \cdot 10\) in half: \(\frac{11 \cdot 10}{2} = 55\).
Now, to get \(1 + 2 + 3 + \ldots + 2009 \), we can imagine lining up our rows and sum each column.
1 + 2 + ... + 2008 + 2009
2009 + 2008 + ... + 2 + 1
-------------------------------
2010 + 2010 + ... + 2010 + 2010
So now we can say with surety, the greatest number of balls you can have where it’s still possible to get stuck is \(\frac{2010 \cdot 2009}{2} = 2019045\). If you want to be sure you can always move balls around, you need at least 2019046 of them.
Wrapping up
We now know how many balls we need to have. But if you remember back, the question asked “For which values of \(n\)” is it possible to rearrange the balls. So we have \(2010n\) balls, and we need \(2010n > 2019045 \). Dividing both sides by 2010, we get \(n > 1004.5\). If \(n\) has to be an integer (we can’t put 1004 and one half balls in each box!), we get \(n \geq 1005\).
So there you have it. The only values of \(n\) for which it is possible to reach the distribution with exactly \(n\) balls in each of 2010 boxes are \(n \geq 1005\). In case anyone asks.