Wrapping Up

This blog post will be the final post in this blog. I was skeptical to the use of blogging about CSC165 but in the end it did have a positive effect. Writing is something I already enjoy doing and putting my thoughts and problems into words helped to create plans to tackle these problems head on. It was a pleasure to learn CSC165 under Professor Heap, who is, without a doubt, the best Professor thus far in my university experience. Hoping to learn under him again in the upcoming years! Last week's blog post went over the Penny Piles problem. My initial approach was to construct a program, as seen in the previous post, but after some testing this program was found to be faulty. For example, it would return that it was not possible to reach a pile with only 1 penny. However, consider the following approach, going backwards:

1 63 

2 62 

4 60 

8 56 

16 48 

32 32

64 0

Simply always moving half over to the right pile allows you to reach one. This one counter example causes my program to not be a viable solution. Let's take a look at the problem using a systematic approach, Polya's approach:

Understand the Problem

This problem forces the solver to determine whether it is possible to reach a certain amount in one drawer from a given starting point. On each of the drawers, the following operations may be employed: L: Iff the left drawer has an even number of pennies, you may transfer half of them to the right drawer. R: Iff the right drawer has an even number of pennies, you may transfer half of them to the left drawer.

Devise a Plan

The first idea was to construct a program that can simulate and determine whether scenarios can be reached. As seen in past weeks blog, a program was created but as disproved above, it is not functional. My next option was to run some manual simulations and try and find a pattern. A tree can be created showing all the possible outcomes with the following starting drawers [64, 0].

Carry Out the Plan

The following is a tree constructed starting with drawers [64, 0]:

64
32 32
16 48
40 24 8 56
20 44 52 12 4 60 36 28
10 54 42 22 26 38 6 58 2 62 34 30 18 46 50 14
5 59 27 37 11 53 21 43 13 51 19 45 3 61 29 35 1 63 33 31 17 47 49 15 9 55 23 41 25 39 7 57

Due to formatting issues, the tree is presented left to right. However, this is enough for our needs as we are only worried about whether each tree node is there. If we look through this tree, every value from the range 0 to 64 is present. Anything more than 64 is not reachable only because we only started with 64 pennies, it's not possible to just create more pennies. If you know how, let me know.

Using the hint given on the problem handout, working backwards, we can see the cause of this. This is due to every number being able to be represented in binary or with multiple additions of 2^n, n \in N.

Take for example the number 13:

13 = 2^3 + 2^2 + 2^0 = 8 + 4 + 1 = 13

Conclusion

In conclusion, since we are relying on if a number can be represented in binary, it can be concluded that ANY number can be created when dividing piles with an even number. The only time this is not possible would be when the starting piles are both odd and no operations can be carried out.

It was a pleasure to write these blogs and learn under Professor Heap and TA Lala. I learned a lot and this knowledge will defiantly come into use in my future classes and career. Let's hope second year's professors and classes are as enjoyable as this one. :)