Week 7: Penny Piles Pose Peculiar Problems

Proof territory continues.

This Friday we had a very fun swing at a difficult problem involving moving penny piles. We worked at trying to move 64 pennies (2 to the power of 6) from one bin to the other, dividing the pile in half when it was even. What we found was that 64 pennies can, with the correct series of divisions, give back a pile of pennies of any size between 1 and 64. For instance:

Operation L: take 1/2 left drawer, put in right (left drawer must be even)
Operation R: take 1/2 right drawer, put in left (right drawer must be even)
(Drawer 1, Drawer 2)

To get the number 37, we must perform:
L(64, 0) -> (32, 32)
R(32, 32) -> (48, 16)

Now we have (2^5, 2^5) becoming (3*2^4, 1*2^4). This point is significant because we no longer have only powers of 2, but we now can use multiples of 3 to produce odd numbers. This will be handy for reaching 37, though it is not a multiple of 2 or 3 (in fact, it's a prime - but it can be multiplied with 2 and 3!)

R(48, 16) -> (56, 8)
L(56, 8) -> (28, 36)
L(28, 36) -> (14, 50)
.
.
.

Okay, this is taking too long.
What essentially occurs is that we must consider two numbers where the sum is 64 and one number is 37. Obviously, the other number in this scenario is 27, so let's think about those two for a minute.

27 is also prime, but its double is 54, which may be a bit more manageable. When one number is 54, the other is 10 - halving 54 here would thus get us our 37. We're working backwards towards the solution...
So now our aim is to get to 54, but let's say 10 because that sounds easier (10 is small and we know its multiples well, while 54 is a bit big and unwieldy). To get 10, we'd need to have (20, 44) before - to get that answer, we'd need to have (40, 24) before.

Let's work from here: (40, 24) is the same as (8*5, 8*3). That sounds fairly manageable, given that our starting number is 8*8. To get the (5, 3) division, let's just work within that area:
L(8*8, 0) -> (8*4, 8*4)
R(8*4, 8*4) -> (8*2, 8*6)
L(8*2, 8*6) -> (8*5, 8*3)

Now we can take the final steps to get 37. We'll have to break the 8s apart, so let's just use powers of 2 from here on to show the factors.
L(5*2^3, 3*2^3) -> (5*2^2, 3*2^3+5*2^2) --matching the factors--> (5*2^2, 11*2^2)
L(5*2^2, 11*2^2) -> (5*2, 11*2^2+5*2) --matching the factors--> (5*2, 27*2)
R(5*2, 27*2) -> (5*2+3^3, 3^3).

And 5*2+3^3 is 37. Hurray! Thus, by working backward, we are able to determine what steps to follow through solving the problem.
I'll add more to this later.