# Can you distribute the balls equally into 2 boxes?

You have 2 boxes and an even number ($$2n$$) of balls in the first box. Your goal is to distribute the balls equally into the two boxes, so that each box contains $$n$$ balls. You must obey the following protocol:

Step 1, move exactly 1 ball from one box to the other box.

Step 2, move exactly 2 balls from one box to the other box.

Step 3, move exactly 3 balls from one box to the other box.

$$\vdots$$

Continue until you come to step $$k$$, when you first find that each box contains less than $$k$$ balls. If this happens, you go back to step 1 and start from there again. So on and so forth.

Example: if $$n=5$$, a possible plan is (10,0)-(9,1)-(7,3)-(4,6)-(0,10)-(5,5); if $$n=2$$, you can check that it can't be done.

Question: is there a threshold $$N$$ for $$n$$, such that as long as $$n\gt N$$, you can always find a plan to equally distribute the balls?

We can show that such a threshold

exists without explicitly constructing it.

To that end let us establish a simple sufficent win condition:
Let S be the current step size and 2D be the difference in numbers of balls i.e. the boxes contain n-D and n+D balls.

If (1) S < n - 2D then we can move S from the box with fewer balls to the other one and then S+1 the other way. This will decrease D by one and increase S by 2. The new position therefore has step size S' = S+2 and box difference 2D'= 2D-2. In particular, they satisfy the same constraint (1) as S and D. Consequently, we can repeat this until D becomes 0.

From the starting position, let us make the maximal number K of moves in the same direction such that the first box still contains no fewer balls than the other. The D<S=K+1 and n = S(S-1)/2+D. In particular, D and S are both $$\mathcal O ( \sqrt n )$$ and (1) must hold for n large enough.

• 2D' =S' < n - 2D' 2D-2 is this a typo?
– Eric
Aug 7 at 7:41
• @Eric yep, probably hit the touchpad while typing. Thanks for pointing it out. Aug 7 at 8:08
• +1 Nice proof. Further more, it seems to me this method holds for any initial distribution of balls in the boxes, not just 2n balls in one box.
– Eric
Aug 7 at 8:13
• @Eric, that is correct (as long as the total is even). Aug 7 at 8:52
• Can we claim something even more general? Let's label the boxes 1 and 2. If we want to change from any initial distribution of balls to any other distribution, can we always succeed if the total number of balls are sufficiently large?
– Eric
Aug 7 at 16:11