Can you distribute the balls equally into boxes

combinatoricselementary-number-theory

You have $n$ boxes and $mn$ balls in the first box. Your goal is to distribute the balls equally into boxes so that each box contains $m$ balls. You must obey the following protocol:

Step 1, move exactly $1$ ball from one box to another box.

Step 2, move exactly $2$ balls from one box to another box.

Step 3, move exactly $3$ balls from one box to another box.

$\vdots$

Continue until you come to step $k$, when you first find that every 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=3,m=2$, a possible plan is 600-510-330-303-204-222.

Question: Can you always succeed for sufficiently large $n$? (i.e. does there exist $N$ such that $\forall n\gt N,\forall m$, there's a plan to equally distribute the balls?)

Update: Since I strongly suspect the answer to my question is yes, let me frame the problem in a more general (and hopefully more interesting) form:

The boxes are now labeled. Your goal is to transform any $m$-ball-in-$n$-boxes distribution into any other such distributions, for all $m,n\gt 0$.

Question: is it true that you can succeed for all but finitely many such transformations by following the aforementioned protocol?

Best Answer

It can't be done when $n=m=2$.

The initial position is $40$. The only legal move is to $31$. Now the only legal move is to $13$ from there we must move back to $40$. Now we can move to $04$, but $k=5$, so $k$ reverts to $1$, and the position is symmetric to the one we started with.

EDIT

Suppose that $n>2$. While $k<m$, transfer balls between boxes $1$ and $2$. If both boxes have at least $k$ balls, it doesn't matter which you transfer from. When $k=m$, transfer $m$ balls to box $n$, and never touch these again. Continue transferring balls between boxes $1$ and $2$ until $k=m$ again, and then transfer $m$ balls to box $n-1$, and never touch them again.

Continue this process, until there are $m$ balls in each of boxes $3,4,\dots,n$ and $m$ balls in boxes $1$ and $2$ collectively.

If we can prove, for a given $m$, that we can solve the problem when $n=2$, regardless of the initial state of the two boxes, then the above discussion proves that we can solve the problem for this $m$, for all values of $n$.

I'll prove it for $m=3$. First, we can transfer balls between boxes $1$ and $2$ until $k=1$ so we can assume that $k=1$ to start.

Then we have $$ (6,0)\stackrel1{\rightarrow}(5,1)\stackrel2{\rightarrow}(3,3)\\ (5,1)\stackrel1{\rightarrow}(4,2) \stackrel2{\rightarrow}(6,0) \stackrel3{\rightarrow}(3,3)\\ (4,2)\stackrel1{\rightarrow}(3,3) $$ The other cases are symmetric to the ones already considered.

The fact that it's not solvable when $n=m=2$ doesn't prove that it isn't solvable when $m=2$ and $n>2$.
It's easy to prove that it's possible for any $n$ when $m=4$, in the same manner as above. I've also done it for $m=5$. It's the same procedure, just a hair longer.

In an earlier edit I conjectured that it wasn't true for $m=2$, except in the trivial case $n=1$, but the OP showed how to do it for $n=3$ in the question. I now believe it's true in all cases but $n=m=2$, but I can't prove this. It should be possible to prove it for $m=2$ by adapting the proof above, using $3$ boxes instead of $2$, and of course, it's easy for $m=1$.

UPDATE

The proof I outlined for $m=2$ works. There are $6$ inequivalent configurations to check.

I wrote a python script that proved it by brute force for $3\leq m\leq 250$.

def test(m):
    if m<=2:
        raise ValueError("m must be >= 3")
    for p in range(m):
        if not possible(p,m):
            print(p)
            return False
    return True

def possible(p, m):
    # State is described as (p,k) where p is the
    # number in the smaller pile, and k is the number 
    # of balls to to move.
    # We assume that state (r,1) is possible for r<p.
    
    visited = set()
    level = 1
    S = { }
    S[1] = { (p,1)}
    while level > 0:
        while S[level]:
            p, k = S[level].pop()
            visited.add((p,k))
            if p == m:
                return True
            level += 1
            S[level] = set()
            if k > 2*m - p and (p,1) not in visited:
                S[level] = {(p,1)}
            if p < k <= 2*m-p:
                p1 = min(p+k, 2*m-p-k)
                if (p1, k+1) not in visited:
                    S[level] = {(p1, k+1)}
            if k <= p:
                if (p-k, k+1) not in visited:
                    S[level].add((p-k, k+1))
                p1 = min(p+k,2*m-p-k)
                if (p1, k+1) not in visited:
                    S[level].add((p1, k+1))
        level -= 1
    return False

for m in range(3,251):
    if not test(m):
        print(f'Test failed for {m}')

No exceptions were found.

Related Question