Piles of Pennies Problem & Last Post

Hi!

For my problem solving episode I decided to choose the Piles of Pennies problem from the problem-solving wiki website the professor gave us. The question was:

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 can contain 48 pennies using the two following operations? Also Can you arrange things so that one of the drawers can have any number of pennies in the range [0, 64] using the two following 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.

The first step to solving this problem is understanding the problem:
In order to solve this problem I must show that I can create two piles, one of size k (where 0<=k<=64) and the other of size 64-k. First I want to show that I can create a pile where k is 48, and then I want to show that I can create a pile where k is any integer in [0, 64].
Also, note that you can only perform the operations when the respective drawers contains an even amount of pennies.

The second step to solving this problem is to devise a plan:
First, I will check that the drawer with all the pennies contains an even amount of pennies, otherwise I cannot perform any operations on it. Also the only choice I have for my first move is to split the left drawer of 64 pennies into two so that the left and right drawers have 32 pennies each.
Also after the first move, one idea is to perform the L and R operations in different combinations in order to get a drawer that will contain 48 pennies, and then continue to perform operations until we show that a drawer can contain any amount of pennies between 0 and 64 inclusive.
This problem kind of reminds me of the three jugs problem where you have 3 jugs, one of size 3, one of size 5, and one of size 8 where the size 8 one is filled fully with water and you pour the water into jugs to try to get a result where two jugs are filled with 4 liters each.
I think I should start here by trying to find a combination of operations until I get k to be 48 first. Then I will try to find a pattern if I can to solve the next part.
Also to see if k can be anything between 0 and 64 inclusive, I think constructing a tree with all possibilities would be good.

The third step is carrying out the plan:
To get k = 48. We can perform the L operation twice or perform L then R:
Left drawer: 64 Right drawer: 0
Left drawer: 32 Right drawer: 32
Left drawer: 16 Right drawer: 48
Therefore you can arrange things so that one drawer has 48 pennies.

Construct a tree (here is a picture because I was too lazy to type it):

Sorry for the mess, I'm not that skilled with the pen as you can see.

Anyways, from the picture, an arrow from the left value in the coordinate means performing the L operation and an arrow from the right value in the coordinate means performing the R operation. The left value and the right value in the coordinate represents the number of pennies in the left and right drawer, respectively.

As you can see, a drawer can contain any amount of pennies, k, where k is an integer between 0 and 64 inclusive, through the L and R operations.

Looking back:

Looking back on how I approached this problem, I feel that there are other ways to solve it. I think I took the easiest, most simple way to solve the problem, but I think there are more efficient ways of solving it. There must be a way to solve this by induction.  Although, creating tree diagrams are very effective in solving problems where you deal with combinations. In the end, you CAN arrange the pennies, through the 2 operations, so that a drawer can contain any amount of pennies between 0 and 64 inclusive.

Also, in other related news. This will be my last post for this blog. I know, it's a sad moment. Don't worry, if you want to creep my thoughts or stay in touch with me, you can follow me on twitter: @ZainManji

Overall, I really liked this course and the professor. Professor Heap made the concepts easy to understand and even interesting. I really liked how he set up the course so that tutorials involved quizzes which could help you learn how to tackle different kinds of problems with the concepts learned in lecture. They also really prepared me for the term tests. I hope to have him again/work with him later on in my university career.

Anyways,

Peace out!

Last Week!

Hey everyone!

I'm really excited for this week to begin because it's the last week of classes! Also this means that final exams are this much closer than before, but I only have 2 final exams this semester so I don't mind. This also means that the holidays are coming soon, which for me means spending time with family and friends. Anyways, I know I said that my next post would be the problem solving episode but, yet again, it's not. In the next day or two I will be posting that, out of pure procrastination. Sorry guys.
Anyways, we are learning about DFSA's and regular expressions in class these days. I actually enjoy this topic, because I like the topic. Constructing FSA's to me is sort of solving a puzzle. You have to consider all the possibilities before the construction and it's very easy to miss a possibility that will drive to DFSA to be incorrect. Also I took software design over the summer where we learned about regular expressions, so it's a familiar topic to me. I always enjoy topics which I am already familiar with because it's easier to understand. The semester is almost done which means that this blog will soon come to an end. I will give my final thoughts of the course in my last post. Also the last quiz is tomorrow, so I am hoping to end the quiz season off on a positive. I want a 2/2!

Talk to you soon.

Cheers!