One At A Time

Alright, time to finish off the solution to the balls in jars problem from before.

The essential proof is that it is possible to find an algorithm that will move from a position (a,b,c), with a>b>c, to a position (x,y,z) such that z is less than c. Thus by repeating this algorithm no more than c times, you must reach zero (given that we can only have integer values).

OK, suppose we start in some position. Call the bucket with the most marbles A, the one with the fewest marbles C, and the other one B. The names of those jars will not change throughout the algorithm, specifically even though C has the fewest at the start it might not at some later point. Let a, b, and c be the number of marbles in jars A, B, and C respectively. Note that even though A, B, and C will not change throughout the algorithm, the values of a, b, and c will.

The algorithm is: Check the value of floor(b/c). If it is even, move marbles from A to C. If it is odd, move marbles from B to C. If C has more marbles than B then stop, otherwise go back to the start.

Simple enough, now, to prove it works. We must prove that at the end B will have fewer marbles in it than C started with.

At the start, we know that b is greater than c, let us write b=qc+t with t less than c, so q being the floor of b/c. For this proof, we will not change the values of a, b, and c, I will assume those values are locked at the start.

Let us suppose b is not at least twice as big as c, so then q=1 and when we move marbles from B to C (as per the algorithm), B will have t marbles in it, and t is less than c.

Now, if q is bigger than 1, I will show that the algorithm will reduce the number of marbles in jar B without changing the value of t, so eventually q will be 1.

So, if we suppose q is even, so we move marbles from A to C. Now C contains 2c, and B contains b. Since b=qc+t=(q/2)(2c)+t, so b mod c and b mod 2c both give t (note that q being even was needed).

If q is odd, we will move marbles from B to C. Now C contains 2c and B contains b-c. Since b=qc+t we can also then show b-c=((q-1)/2)(2c)+t, so b mod c and b-c mod 2c both give t (in this case q being odd is needed).

Each time, B contains fewer marbles, so eventually q will be 1 and then next move B will have t marbles, which was less than the starting value of C. So, this finishes the proof. One simply needs to repeat the algorithm many times (renaming the jars A, B, and C after each iteration) to win the game.