SLOG Week 6

This week we were introduced to a problem called penny piles.

Understand the problem

You start with two side by side drawers. The left one contains 64 pennies while the right one contains zero pennies.

- If the left drawer has an even number of pennies, you may transfer half of them to the right drawer. YOU CANNOT DO THIS IF THE LEFT DRAWER HAS AN ODD NUMBER OF PENNIES.

- If the right drawer has an even number of pennies, you may transfer half of them to the left drawer.
YOU CANNOT DO THIS IF THE RIGHT DRAWER HAS AN EVEN NUMBER OF PENNIES.

Thus we can conclude that you may are unable to do take away pennies from any drawer that has an odd number of pennies.

WHAT WE WANT TO KNOW:

- Can we arrange things so that one of the drawers has 48 pennies using the 2 methods available above?

- Starting from the same initial position (left drawer: 64 pennies, right drawer 0 pennies) can you pick any number in the range [0,64] and obtain that number on one of the drawers using the two methods given? If not, which ones are impossible to achieve?

- What happens when you start with a different number of pennies in the left drawer?

Devise a plan

During class, I tried many different approaches to this question. This included trying to find a pattern in which I could relate to with a mathematical formula which could get me any number which worked.

What I got was two formulas which would calculate the number of pennies needed to be on each side to achieve a number.

( Even or Odd Number, Other side)  aka (what we want, what the other side needs to be)

Where n is a generic integer number

Even Number: ( 2^n , 64 - 2^n)
Odd Number: (2^n + 1, 64 - 2^n - 1)

This approach did not really lead me to an answer since it didn't answer any of the questions above.

Thus, I decided to make a tree diagram because that would should all the possible results and would be able to answer to first two questions.

Carry out the plan

As shown from the above tree diagram, every even number in the range [0,64] even number is achievable and will eventually become an odd number. When this happens both sides of the drawer will become odd since even + odd = odd.

Therefore we have found out that since all numbers in the range [0,64] exists on the tree diagram, you can pick any number in the range [0,64] and arrange things so that one of the drawers has that number of pennies using the two methods of arrangement available to us. Since this is true, we can also arrange things so that one drawer has 48 pennies.

However, this is not the case if we started with a different number of pennies in the left drawer. This is because if we start with an odd number of pennies in the left drawer, there will be an odd number of pennies in the right drawer. Since both drawers have an odd number of pennies, it is impossible to use either of the methods of arrangements given to us.

We have thus answered the three things we want to know.

Looking Back

The tree diagram looks as if it has effectively solved the problem. However, this method would prove to be very tedious and inefficient had we been given a bigger range such as [0,1000]. A better way of doing this may be to write a program to compute all the combinations for you or maybe to actually use a mathematical proof.

OTHER SLOGS

I really liked how John could find  a way to determine whether the statement is true or false. From it, I learned that it is probably best to do this first rather than mindlessly diving in to discover every possible solution like I did previously.
http://kimjohnlim.blogspot.ca/2014/12/slog-week-11.html?showComment=1417660528863