Two In One

Alright, time for the partial solution to the balls in jars problem from last time.

I guess since the two-jar problem is a decent amount easier, I'll solve that out first.

First of all, it is absolutley trivial to see that if the total number of balls in the jars is not an even number, there will be no way to win, since to win you must first arrive at a position of the form (p,p). Next, it is easy to see that any common divisor has no effect on the ability to win from a position, that is to say: the position (p,q) is winnable iff the position (np,nq) is winnable.

At this point, we might be inclined to work out a few winning positions. OK, so what are the winning positions of the form (1,q)? Well, clearly (1,1) is a winning position, and (1,q) can only be a winning position if q is odd. From the position (1,q) we move to the position (2,q-1), but since q is odd for any position of interest this is the same as (1,[q-1]/2) so if we suppose this is another position, say (1,k), we see that q=2k+1 so if (1,k) is a winning position then so is (1,2k+1). From here we can list off the positions as (1,3), (1,7), (1,15)... clearly (1,q) seems to be a winning position if q is 1 less than a power of two. You can prove that by induction if you like, and with a bit more work we can also be sure that there aren't other winning positions of the form (1,q), but I won't bother with that yet.

Next, what about positions of the form (3,q)? Well, first of all q=1 would be a winning position. Next, from (3,q) we can move to (6,q-3) (this assumes that q>3, but other positions are finite enough anyway). Now since we might as well assume q is odd, we can half this position to (3,[q-3]/2) so calling this (3,k) again, we see that if (3,k) is a winning position then so is (3,2k+3). Listing off positions we can see that the winning positions seem to be (3,1), (3,5), (3,11), (3,29)... again summing to a power of two. This makes it seem that a position (p,q) is a winning position iff the sum p+q is a power of two. Well, thats easy enough to disprove, (3,9) is a winning position, but it is merely a multiple of 3 away from (1,3).

The main thing that will finish this off is the realiziation that once you have divided off any multiples in your problem, no new ones will show up, besides 2, and that one will show up every move. Lets prove that. Suppose we are in some position (p,q) with p and q both odd (so that their sum is even, but we do not need to divide off an overall 2), and we assume that p and q are not both multiples of some prime number n (n>2). Now we move to (p-q, 2q) (setting p as the larger one), I claim that p-q and 2q are also not both multiples of n. If they were then q would be a multiple of n (since 2q is) and then p would be (since p-q is and q is). Naturally this argument won't work for n=2, an overall multiple of 2 shows up every single move.

Now I will prove the main result: from position (p,q) with p and q having no common factors, we are in a winning position iff p+q is a power of 2.

You can prove one direction by induction. Prove it for p+q=2^n. It is trivial for n=1, then if it is true for n=k and you are in position (p,q) with p+q=2^(k+1) you can make one move and then half p and q so that p+q will now equal 2^k.

For the other direction we must show that if p+q is a multiple of a prime other than 2 and p and q have no common factors, then it is a losing position. Suppose p+q is z*k where z is a prime other than 2. k must be even, for if p+q is odd then we are trivially in a losing position. In order to win, we must first reach (z*k/2, z*k/2) but we have already proven that once you have divided off multiples, no new ones can show up. A new multiple of z (for z>2) cannot happen, so the position (z*k/2, z*k/2) cannot be reached, so the game cannot be won.

This finishes the proof. While working on the problem I also noticed that the legal move from (p,q) is to (2p,2q) mod p+q, which I thought was sort of cool. Perhaps people who are better at number theory than I can make use of that. Anyway, feel free to try to use this to solve the three jar problem, I was never able to.