This week we were introduced to the penny piles problem. In class my partner and I drew a tree to see if there were any numbers from 0 to 64 that were not included in a tree where left branches represented the L operation and right branches represented the R operation.
We made some interesting discoveries. Firstly, any number you pick in this range can be achieved by performing these operations because they were all in the tree. Secondly, every new step introduced numbers that had not yet been introduced and would not be introduced again. That is, if you were able to achieve a certain number of pennies by making 3 operations, you could not achieve that number by making less than 3 or more than 3 operations. We also found that the leafs in the tree (nodes where the amount of pennies in each drawer was odd) had a depth of 6 (it took 6 operations to get to an odd number), and we mused that since 64 = 2 ^6, this may not be a coincidence.
Obviously we used Hint 3 by drawing a picture, but I also like Hint 1, which was to work backwards. It would be interesting to devise a Python program that would prove that for any number you inputted, you could work backward until you get back to 64 in one drawer, which would prove that every number is in the tree. To see if this tree worked for any amount of pennies to begin with, not just 64, I would make a program that took two parameters, the amount of pennies you hope to achieve in one of the drawers, and the total amount of pennies you begin with (64 in this case). My prediction is that if you entered any number of total pennies such that the total could be expressed as 2^ x where x is a natural number, and the amount of pennies you hope to achieve in one of the drawers is a natural number between 0 and the total, the program would return 'True.'
No comments:
Post a Comment