Problem solving session penny piles

This problem solving session is based on the lecture in 10.28 which the problem of penny piles is discussed.

A problem solving session contains four parts:

1. Understand the problem

2. Devise a plan

3. Carry out the plan

4, Look back,figure out when and how you are stuck

Each part would be discussed carefully.

1. Understand the problem

To rephrase the question: You have two number 64 and 0. You can do an operation to change the number. The operation could be done if the number is in even, you divide that number by 2, and add the divided number to the other.

For example, now one have two number 48 and 16. If you do this to 48, then it becomes 48/2 = 24 and the other number becomes 12+24 = 40. Or, you do this to 12, then it becomes 12/2 = 6 and 48+6 = 54.

We want to prove that any number in the range [0,64] are able to achieve.

2. Devise a plan

Initially we have number 64 and 0, and the only operation we can do is to divide 64 by 2 and add 32 to 0, so it becomes 32, 32. Here since the numbers are the same, the next step would change it to 48 and 16.Then we have two choices which are 24, 40 or 56, 8. Then four 12, 52; 44, 20; 28, 36; 60, 4. So far the question has already become very complicate and would be even more complicate as there are more and more possibilities. Anyway, from the sample we have seen so far, we can see the pattern that they are all even number. That is quite reasonable as an odd number means we can no longer do operation to it. For example, 17, 47 seems hard to get. If we think it in a reverse way, the answer is quiet obvious. 47*2>64, so the only possible choice is 17*2=34 and the previous numbers are 34, 30.Again, 34*2>64. Thus, the previous one is 4,60. Then 8, 56. Then 16, 48. Then 32, 32. Then 64, 0 which is the beginning.

Now it is easy to see the pattern, we do it reversely. Sdince we have the last step and we could assume the previous step until we get 64, 0.

3. Carry a plan

We have an input (A1, A2)

Let

While  (A1,A2) != (64, 0) or (0, 64):

    If A1>32:

        A2 = A2/2, A1 = A1+A2/2

    else:

        A1 = A1/2, A2 = A2+A1/2

4. Figure out when and how you stuck

In this problem solving session, I stuck for a long time when facing to the data I collected as it is hard to find the pattern. Then at one point, I got the idea to think reversely and solve the problem quiet easily. I think this is the key for the question.