Can you distribute the balls equally into 2 boxes?

Question

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?

Answer 1

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.