Interesting problem handout from lecture today. It is called the Penny Pile Problem. Basically you have two boxes, the left box contains 64 pennies and the right contains nothing. Now, there are two operations that you are allowed to use in order to move pennies from one box to the other.
L: If the left box has an even number of pennies, you can transfer half of them to the right box. If the left box has odd numbers of pennies, you can not use this operation.
R: If the right box has an even number of pennies, you can transfer half of them to the left box. If the right box has odd numbers of pennies, you can not use this operation.
Now, the problem is to arrange things so that one of the boxes has 48 pennies using the operations from above.
So, let's just carry out the operations.
(64,0)
(32,32)
(48,16) - Done!
Well, that was easy.
Now, are we able to choose any number from a range of 0 to 64 and arrange it so that we are able to achieve that number? I think it is definitely possible.
Let's begin from (64,0), the only step is to divide the pennies into two piles each containing 32 pennies. Therefore, I think I will tackle the problem from 32 since once we reach 32, we are able to get back to 64. From here on, my intuition is to work backwards from the chosen number and reach 32. If the chosen number is bigger than 32, then the other number can be arranged to become 32 and reach 64.
No comments:
Post a Comment