week[6]_pennyPiles

This week we finish the second part of our course, the proofs, and start on the final part, the algorithms, but there aren’t much about it, just a first taste. For proofs, we continued on proving cases and did some review. Assignment 2 is coming I believe.

Algorithm for us now is only like 3 symbols: big-O(<=), big-omega(>=) and big-theta(omega<=f<=O). I think I can manage it as long I remember the relations between them.

Other than that, we are asked to talk about penny piles.

Penny piles is a problem that given the left drawer has 64 coins, the right drawer is empty, then:

If L has even number of coins, transfer half to right.

If R has even number of coins, transfer half to left.

So basically in this case the number of the two piles are 64-0, 32-32, 48-16, 24-40, 44-20, 22-42, 43-21. The questions is what about starting with a different number of coins in the left drawer.

As far as I can find from internet and course resources, this problem can only perfectly be solved by using a proving technique called induction. Unfortunately we are not able to learn it in CSC165, it’s a huge part in CSC236 though. The general I idea is assume a “function” true, and its input is n, such as P(n) and as long as we can prove P(n+1) is true, then P(n) is true. This proving technique sounds more fun and more powerful. Also an interesting thing I’ve found is if something is hard to solve, assume it is true and most likely you are on the right track, lol.