Week 10 and Problem Solving Episode

This week we continued with big-O and big-Omega proofs.  I found that I was able to understand the material well.  There were no real confusing aspects of the proofs.  This weekend Assignment 3 was to be assigned, however, all the computer science websites were down, so we were unable to access it.  As a result, the due date was delayed by three days.

Below is my problem solving episode.
----------------------------------------------------------------------------------------------------------------------------------------------
On October 24th, we had our second in-class problem solving session.  This problem involved manipulating piles of pennies in two drawers.  The problem read:

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 combinations of the following two operations, l and r?
l: If the left drawer has an even number of pennies, you may transfer half of them to the right drawer.  If the left drawer has an odd number of pennies, operation l is disallowed.
r: If the right drawer has an even number of pennies, you may transfer half of them to the left drawer.  If the right drawer has an odd number of pennies, operation r is disallowed.
Choose another number in the range [0,64].  Starting from the same initial position, can you arrange things so that one of the drawers has that number of pennies? Are there any numbers in that range that are impossible to achieve? What about starting with a different number of pennies in the left drawer?

1. Understand the Problem
This problem has multiple parts:

• starting with 64 pennies in the left drawer, can you use operations l and r so that there are 48 pennies in one of the drawers?
• in the range [0,64] are there any numbers that are impossible to achieve?
• How does the answer to question 2 change if there are a different number of starting pennies?

2. Devising a Plan
I decided to start with the first question as it seemed the easiest and a precursor to question 2.  My original plan was to create a table with the two columns being the right and left drawers and keep track of which operations I performed to reach 48 pennies.  I would then extend this plan to include all the numbers between 0 and 64.

3. Carry out the Plan
I was able to answer the first question quickly as it only took three utilizations of operation l.  My first table looked like this:
Right Drawer                     Left Drawer
64                                       0
Operation l
32                                       32
Operation l
16                                       48

I then attempted to answer question 2 using this same format.  I started at 0 and worked my way up eventually reaching 25 before I realized that my plan was too time consuming and that there was a better and faster way to solve this problem.  So, back to step 2.

2. Devising a New Plan
My second plan entailed constructing a tree of all the possible combinations of numbers from all possible combinations of operations.  From my first plan, I noticed that all the pairs of numbers summed to 64, so this would be a good way to check my answers and ensure that I have covered all the numbers.

3. Carry out the New Plan
The number tree was much faster and after completing it I found that (as I had predicted), it was possible to have one of the drawers hold all the numbers between 0 and 64 inclusive.  My tree for 64 starting pennies looked like this:

4. Looking Back
I was able to check my answer by checking that all the numbers between 0 and 64 were in my tree.  Since the last question is an extension of the one just answered, I have included my solution to it here.  Based on the results with 64 pennies, my original prediction was that the results would be the same for all even numbers (odd numbers wouldn't work because they are not all divisible by some common number, like evens are).  So I decided to try some other even numbers.  I started with 32:

 

 32 worked fine.  What about 8?

 

8 also works.  But then I tried starting with 12 pennies:

 And I got stuck at 9 and 3.  So it seems my original prediction was wrong.  So why do some even numbers work and others do not? What do 8, 32, and 64 have in common?  I noticed that those three numbers are all powers of 2, whereas 12 is not.  A quick check of other powers of 2 (like 4 and 16) and non-powers of 2 (like 10) confirmed my theory.  This answer raised another question: what is the relationship between the most number of steps it would be necessary to perform and the starting number?  Well, with my knowledge that the numbers that work are powers of two, and based on the trees that I drew, it became apparent that the log base 2 of the starting number corresponds with the final tier of numbers in each tree.  Finally, it is also interesting to note that all the numbers in this final tier are odd and that odd numbers only show up in the final tier.  With this information, it is possible to predict whether or not a number follows the same pattern as 64 and how many operations it would take to obtain an odd number of pennies in one of the drawers if given only the starting number of pennies.