Undergrad Simple, almost "intuitive" conjecture, hard or impossible to solve?

[fluidistic]

Hello,
I have posted a problem (on math stack exchange) I was given for fun by an uncle, who doesn't know whether the proof is possible to establish. I tried my best and failed so far. I don't think I can solve the problem with my current knowledge and I would love to know if you can find a solution or at least have some ideas.
Problem statement:

There are initially three boxes, labelled $A$, $B$ and $C$. $A$ contains $3n$ balls, with $n\geq 5$ a natural number. At step number $k$, one withdraws $k$ balls from any box and place it into any other box. Show that it is always possible to end up with $n$ balls in each boxes after exactly $n$ steps.

So far I have been able to show that there is no possible proof by induction, I believe. The reasoning is that if we start with a solution that works for $n$ steps, then we cannot make any further step because it would mean to withdraw $n+1$ balls from any box, making the number of balls negative in that box, which is not allowed.
So maybe number theory can offer a way to tackle the problem?

I have written a Python program that outputs the solutions for a given $n$, and I have stared hard at them (their number grows quite quickly with $n$. There are 36 or 72 solutions for $n=9$ for instance, starting from 1 or 2 solutions for n=5 depending on whether $B$ and $C$ are distinguishable). No luck, I couldn't notice obvious patterns or ways to create solutions. Some of them look almost trivial (i.e. withdraw balls from box A most of the time and place them into either $B$ or $C$ and then at the final step(s) withdraw from $B$ into $C$ or the opposite) but in general there is no such "trivial looking" solution. So I am not able to find an algorithmic or automatic way to build a solution from scratch.

 

[Stephen Tashi]

An algebra lovers version of the problem:

Let $T_k = (\frac{A^k}{B^k} + \frac{B^k}{A^k} + \frac{A^k}{C^k} + \frac{C^k}{A^k} + \frac{B^k}{C^k} + \frac{C^k}{B^k} )$

If $n \ge 5$ must the product $A^{3n} \prod_{k=1}^n T_k$ contain a term of the form $A^nB^nC^n$ ?

 

[gmax137]

this kind of problem is way beyond me. I did have an idea though. What if you think backwards -- you start with n balls in each box, and move n, then n-1... to end up with all balls in box 1.

 

[mfb]

An algebra lovers version of the problem:

Let $T_k = (\frac{A^k}{B^k} + \frac{B^k}{A^k} + \frac{A^k}{C^k} + \frac{C^k}{A^k} + \frac{B^k}{C^k} + \frac{C^k}{B^k} )$

If $n \ge 5$ must the product $A^{3n} \prod_{k=1}^n T_k$ contain a term of the form $A^nB^nC^n$ ?

Are you sure this avoids problems with negative numbers? As an example, if you want to move 1 ball with steps 1 and 2 then simple algebra tells you that -1+2=1, you could do that - but in practice you cannot, because you can't leave -1 balls then add 2 to get 1 ball.

 

[Stephen Tashi]

I would love to know if you can find a solution or at least have some ideas.

So far I have been able to show that there is no possible proof by induction, I believe.

You only tried a weak form of induction. There are techniques called "strong induction".

Some ideas:

If a solution exists for $3n$ balls, then after step $n-1$ we had a situation where the occupancy numbers were $\{2n,n,0\}$ (in some order).

Consder the case of $3(n+1) = 3n+3$ balls. Let $w = n-r$ for some $r$ such that $w \ge 5$. After step $n-r -1= w-1$ we could have arrived at the occupancy numbers $\{2(w) + (3n+3 - 3w) , w, 0\}$
We can do this by pretending we are solving the problem for the case of $3w$ balls (i.e. for the initial occupancy numbers $\{3w,0,0\}$) Using that solution we distribute $3w$ balls and have $(3n+3 - 3w)$ balls "left over" in the box where they began.

This opens up the idea of assuming we begin with the situation $\{ 2(w) + (3n+3 -3w), w, 0 \}$ at step $n-r-1$ and trying to show we can reach the numbers $\{2(n+1), n+1, 0\}$ at step $n$. (Thus showing we can reach $\{n+1,n+1,n+1\}$ at step $n+1$).

I don't know whether this can be proven. I'd begin by looking at your numerical examples to see if any of the solutions are examples of the above technique. For example, would the first 5 steps of some solution for the case of 10 balls constitute a solution for 5 balls.

When looking for patterns in the solutions, don't look only at the number of balls in the boxes in each step. Also look at the sequences of numbers of balls that are added and subtracted in each step. Do any sequences for larger numbers of balls contain sequences for smaller numbers of balls embedded in them? Write the data in some way that different orders of the boxes doesn't matter. For example, instead of listing the numbers of balls in boxes A,B,C in the order of the boxes, list the numbers of balls in the boxes from largest number to smallest number. Instead of listing the number of balls removed and added in the order of boxes, list those numbers in the order of the numbers of balls initially in the boxes. For example, (-3,3,0) to indicate removing 3 balls from the box with he largest number of balls and putting them in the box with the second largest number of balls.

 

[fluidistic]

The problem has apparently been solved (via a way) in the math exchange website linked above, for anyone interested.