Pennies problem -- proof

The problem:

You stand in front of two drawers in a table, which you open. The left drawer is empty, but the right drawer has 64 pennies in it, according to your count. On the table is a challenge:

Can you rearrange the pennies so that the left drawer has p pennies in it, where 0 <= p < 64? To accomplish this task, there are two moves that you can make:

R - if the number of pennies in the right drawer is even, move half the pennies to the left drawer.

L - if the number of pennies in the left drawer is even, move half the pennies to the right drawer

Note: closing and reopening the drawers will cause the pennies to magically return to their starting state.

So, to start off with, I could move 32 pennies from the right drawer to the left drawer, resulting in 32 pennies in each drawer. Then, I could move 16 pennies from the left drawer back to the right drawer, resulting in 16 pennies in the left drawer and 48 in the right drawer. Or, I could do 6 R moves resulting in 1 penny in the right drawer and 63 in the left one. Or I could do one R move and 5 L moves resulting in 1 penny in the left drawer and 63 in the right one. Of course, once I reach an odd number, I close the drawers and reopen them to reset the puzzle.

Obviously, if I am to make any move at all, there must be an even number of pennies in one of the drawers. In fact, I must start off with an even number of pennies or I can make no move at all! That implies that, if I am to make a move, there must be an even number of pennies in each drawer, since the total number of pennies must be even to begin with. Suppose that I have j pennies in the left drawer and k pennies in the right drawer. I can represent this by an ordered pair:

(j,k), where j and k are natural numbers

Since j and k must be even (otherwise there is no legal move), there must be natural numbers j' and k' such that j = 2j' and k = 2k', respectively, by the definition of even numbers. That means that, after an L move, for example:

L
(j,k) --> (j/2,k+j/2)

which is the same as:

L
(2j',2k') --> (2j'/2, 2k'+2j'/2) = (2(j'/2), 2(k'+j'/2)) (*)

At this point, it's worth observing that that we need to limit ourselves to starting numbers of pennies that are powers of two. If they are not, then there must be some move that will result in an odd number of pennies > 1. For example, say you start with 12 pennies. One L or R move gets you six in each drawer. The next move gets you 3 in one drawer and 9 in the other. That's all you can do. So, we'll restrict ourselves to powers of two. It is interesting to see if this is possible for any power of two. In other words, if I start with 2^k pennies in the right drawer, where k is a natural number, and 0 pennies in the left drawer, can I find a sequence of moves that will produce 1 <= p <= 2^k - 1 pennies in the left drawer?

Let M be the set of all possible move sequences -- that is, all possible combinations of L and R moves. Let P(k) be the predicate:

P(k) for natural numbers k and all natural numbers p such that k > 0, 0 < p < 2^k, there exists a sequence of moves m_0, m_1, ... m_i, for some natural number i, in M such that (0,2^k) --> (p,2^k-p) after i moves.

Claim: For all natural numbers k, P(k)

Basis: k = 1

Then the starting point is (0,2^1) = (0,2)
There is only one valid move: R, which results in (1,1)
Thus (0,2^1) = (0,2^k) --> (p,2^k-p) = (0,2) after 1 move, m_0
Then P(1) is true

Induction step:

Assume k is a natural number > 0. Assume P(k) is true. We need to show that P(k+1) holds. Indeed, our starting point is:

(0,2^(k+1) = (2*0, 2*2^k)

We know, by the induction hypotheses, that that there exists a sequence of moves m in M such that (0,2^k) --> (p,2^k-p) for all natural numbers p such that 0 < p < 2^k after p_i moves. Applying the same sequences to our new starting point will produce the result:

(0,2*2^k) --> (2p, 2*2^k-2p)

since 2*2*k/2 = 2k for all natural numbers k. From here, we can make an additional move:

(2p, 2^k-2p) --> (p, 2*2^k-2p+p) = (0, 2^(k+1)-p)

as wanted. Thus P(k+1) holds and P(k) implies P(k+1).

Conclusion:

Since P(0) holds and P(k) implies P(k+1), for all natural numbers k > 0, I conclude that P(k) holds for all natural numbers k by the principle of simple induction.

Corollary:

Since every combination of even numbered pairs can be reached, every even-numbered pair can be further divided. Let 2a and 2b be the number of pennies in the left and right drawers such that 2a+2b = 2^(k+1) and a, b > 0. Then 2a and 2b are even numbers, by the definition of even numbers. Without loss of generality, applying one left move to this pair results in the transformation:

(2a,2b) --> (2a+b, b), for all natural numbers a, b such that 2a+2b = 2^k

If b is even, we can repeat the same move until we reach a pair where the right-hand
number is odd. At that point, both numbers are odd, since 2n is even by definition and 2n + m where m is odd results in an odd number. Thus all odd numbers can be reached as well.