So the time has come for me to finish writing this SLOG. CSC236 is coming to an end in around one week and this is the final barrier between me and the exam. You may be wondering why I haven't been writing frequently these days. Aside from exams and last minute assignments, I have been intrigued by this particularly statistical problem: the pile of pennies. I found it while wandering through Piazza and Professor Heap's problem solving website. I've been working on trying to determine which numbers in the set [0, 64] can be obtained and which have not. In this episode, I will be sharing my results.
This is the question:
You are sitting in front of two drawers. The left drawer contains 64 pennies, the right drawer contains nothing. Can you arrange things so that one of the drawers has 48 pennies, using the following two operations:
L - If the left pile has an even number of pennies, transfer half of them to the right pile. If the left pile has an odd number of pennies, operation L is disallowed.
R - If the right pile has an even number of pennies, transfer half of them to the left pile. If the right pile has an odd number of pennies, operation R is disallowed.
What about arranging things so that one of the piles has other numbers in the range [0,64]?
Well right off the bat, we know that we can obtain 64, 32, 16, 8, 4, 2 and 1 through repetitive operation executions on the same drawer. We also have the other drawer that has: 0, 48, 56, 60, 62, 63.
After trying to guess and check my way through the list while writing down the combinations of Ls and Rs, I realized it was quite tedious. I then thought, isn't this problem kind of like recursion? If we consider the step before we achieve the number we desire, wouldn't that be our base case? If the number of items in the drawer is equal to n, then we know that our desired number is on the next step and we're done.
I then thought, what about combining these techniques? What if we noted which combinations were obvious (ie. 64, 32, 16, etc) and then worked backwards through the problem (double the number we want) until we reached an obvious state? So let us try that.
For 3 pennies, we double it: 6. Then performing an operation on the drawer with 6 yields our desired number, 3. Double 6 again. 12. 24. 48. But 48 is an obvious state we achieved earlier! Taking 64-0, performing an operation gives us 32-32 and then performing it again gives us 16-48! Then we just perform it the other way, 40-24, 52-12, 58-6, 61-3. Thus we achieved our 3!
If we were to consider this, we can now add all the "process states" (combinations that we achieved on our way to our desired solution) to our list of obvious states. Now it makes our next number that much easier.
Let's try 5. 5 becomes 10, becomes 20, becomes 40. But we achieved 40 during our search for 3. Thus we can achieve 5. Now add the "process states" to the list of obvious states.
6. 12. 24. 48. 48 is an obvious state.
7. 14. 28. 56. 56 is an obvious state.
9. 18. 36. In this case we have not achieved an obvious state. So let us think more. In a drawer with 36, the other drawer has 28. Note however that 28 is an obvious state. This is important because we don't care if the drawer we want is an obvious state, but that the combination of drawers is an obvious state. Thus we can achieve 9 from 64-0. Let's just do the entire process. 9-55, 18-46 36-28, 8-56, 16-48, 32-32, 64-0.
Following this method, we can repeat all the steps for the remaining numbers, remembering to note obvious combinations along the way. This makes every subsequent computation simpler. While this is an informal proof, we have used our intuition to deduce a method of proving each of the combinations. 64 mini proofs will not take that long but should we have more pennies then a inductive proof will be better suited.
Well my friends, I hope you have enjoyed the journey through CSC236 and I thank you all for tagging along with me. I have enjoyed this course and found the material very stimulating albeit too simple at times. Overall it is a vast improvement over CSC165 from last year. I will be moving forward into CSC265 next semester and will hopefully see you all there!
Thanks for reading!
-ラムダ
