Week 7: Penny Piles

On Friday, we have an interesting lecture. The topic is called penny piles, which means, if you have 64 pennies in a drawer, and 0 in another drawer, every time you can move half of the pennies from one drawer to the other if and only if the drawer has an even number of pennies. When a drawer has an odd number of pennies, the game stops. And the final question is, can you get any number (less than 64) of pennies in a drawer?

My first guess is yes, but I can't tell why, so I started to try. I assumed that there are only eight pennies in the first drawer rather than 64 (which is exactly the second hint). For the first try, I move four pennies to the second drawer, so its 4-4. Again, half to the right and get 2-6. Then either moving from left to right or vice versa will cause the game stop, which results 1-7 or 5-3. And therefore I got all number from one to eight during the moving.

In this way, I guess no matter there are eight or 64 or for all 2^n (n is N+), we can get any number of pennies less than the total number. For the case of total of 16 pennies, I found it hard to write all the possibles in a single list, because each time of moving, I have two different ways of moving. Then I thought up a method, I draw all possible moving in a binary tree, which is just what we are learning in CSC148 (and is just hint 3).

The result is, I found that if we have total number of sixteen pennies, we can also get one to sixteen pennies, which verified my assumption. Meanwhile, I found that except the last line of the tree of sixteen pennies, all the number is just twice of the number in the eight-penny tree. And the last line of the sixteen-penny tree have 8 elements, which are all odd number less than 16. So although this is not a formal proof, we can be quite confident to say that for total number of 2^n pennies, we can get any number of pennies less than 2^n.

To formally prove this assumption, I think we can use mathematical induction. We test the case of 1, 2, 4 pennies manually and assume that if we have 2^k pennies, we can get 1 to 2^k pennies, then we prove that if we have 2^(k+1) pennies, we can get 1 to 2^(k+1).