8
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 2D' =S' < n - 2D' 2D-2 is this a typo? $\endgroup$
    – Eric
    Aug 7 at 7:41
  • $\begingroup$ @Eric yep, probably hit the touchpad while typing. Thanks for pointing it out. $\endgroup$
    – loopy walt
    Aug 7 at 8:08
  • $\begingroup$ +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. $\endgroup$
    – Eric
    Aug 7 at 8:13
  • $\begingroup$ @Eric, that is correct (as long as the total is even). $\endgroup$
    – loopy walt
    Aug 7 at 8:52
  • $\begingroup$ 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? $\endgroup$
    – Eric
    Aug 7 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.