A reflection on the course

CSC236 brought back some of the feelings I had about CSC165. 165 was going great in the beginning, where all we did was learn about proofs, and expanded on methods for proving things. Somewhere in the middle, though, the course switched gears into new-topic-of-the-week mode: Induction, binary digit conversions, Big-O notation, bounds, loop correctness, the halting problem...all of these utilized a few things learned earlier but it wasn't the focus.

Likewise, CSC236 began with methods of induction: mathematical, complete, structural, the well ordering principal. And just like CSC165, around the midpoint, topics became different every few weeks, and while induction was still present, it wasn't the focus. I really prefer the more concentrated course in the beginning, but I guess what happened in the last half is something to expect in an introduction course.

Aside from that, I really enjoyed CSC236. The material is interesting, and the weekly quizzes really keep you in track. Too back there was nothing to keep my blogging on track!

Blue Eyes

A logic problem is hosted on one of my favourite web-comics, xkcd:

http://www.xkcd.com/blue_eyes.html

A group of people with assorted eye colors live on an island. They are all perfect logicians -- if a conclusion can be logically deduced, they will do it instantly. No one knows the color of their eyes. Every night at midnight, a ferry stops at the island. Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay. Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate. Everyone on the island knows all the rules in this paragraph. On this island there are 100 blue-eyed people, 100 brown-eyed people, and the Guru (she happens to have green eyes). So any given blue-eyed person can see 100 people with brown eyes and 99 people with blue eyes (and one with green), but that does not tell him his own eye color; as far as he knows the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and he could have red eyes. The Guru is allowed to speak once (let's say at noon), on one day in all their endless years on the island. Standing before the islanders, she says the following: "I can see someone who has blue eyes."

            Who leaves the island, and on what night?

I stumbled upon it a few years back, tried to figure it out, couldn’t, looked at the solution, and still couldn’t figure it out. At the time I just figured it required some sort of abstract thinking that really didn’t make sense. Fast forward a couple years, where I’m at the end of CSC236, thinking of a problem to post on my blog. From what I could remember of the Blue Eyes puzzle and the (far from formal) solution, it seemed very Mathematical Induction-like. So, with my new knowledge of Induction, what follows is my solution to this “Hardest Logic Puzzle in the World”, guided by Polya’s “How to Solve it” approach.

Understand the Problem

            This is, after all, a logic puzzle, so the answer must of course be logical (and not, for example, looking into a reflective surface and finding out your eye color). The bit about the islanders being perfect logicians allows you to apply computational reasoning to them. It is important that a certain islander can see everyone else’s eye colour, but this alone does not allow him to draw conclusions about their own eye colour. Finally, the Guru only provides info that effects blue-eyed people. So, there is at least 1 blue-eyed person, there are actually 100 blue-eyed people, a blue-eyed person can see 99 other people with blue eyes, and if a person figures out their eye colour, they must leave the island on that night.

Devising a Plan

            It’s always a good idea to reduce the size of a problem to come up with a plan. An interesting thing to ask would be: what if there was only one blue-eyed islander? After the Guru speaks, this islander would look around, see no other blue-eyed people, and logically conclude (since he is a perfect logician) they must be the (at least) one blue-eyed person the Guru mentions. Come midnight, this islander leaves, which we’ll call night 1 to make things simple. No one else ever leaves the island.

            What if there were two blue-eyed people? Then they each see one other blue-eyed person. Being logical, they assume their own eyes aren’t blue. They then conclude that the other blue-eyed person must go through the thinking process above, as if there was only one blue-eyed islander (“they must leave on night 1 if they look around and sees no one else with blue eyes”). Come midnight, however, no one leaves. Since each blue eyed person sees only one other person with blue eyes, but no one leaves the island on night 1, they must logically conclude they themselves have blue eyes. Therefore, two blue-eyed people leave the island on night 2. No one else can logically leave with or after them.

             Three blue-eyed people? They each assume they don’t have blue eyes, and so the other two must go through the process of if there were only two blue-eyed people. But on day 2, of course, no one leaves. They each assume they must have blue eyes and on night 3, three people logically leave the island.

            And so on and so forth. Therein lies something that can be inductively proven: if n people have blue eyes, then they leave on night n. Also, assuming this implies n+1 people leave the island on night n + 1. The base case must be one since the Guru says there must be at least one blue-eyed person. Until the Guru makes another announcement, no one else can figure out their eye colour.

Carry Out The Plan

Proof (by Mathematical Induction):

Define P(n): If n people have blue eyes, they will leave the island on night n

Base Case: n = 1:

            Then the one blue-eyed person looks around and sees no one else with blue eyes

            Then he must conclude he has blue eyes and leave on night 1, so P(1) holds

Induction Step: Assume n∈ℕ, and P(n) holds

            Consider that the island has n+1 people with blue eyes

                        Then each blue-eyed person looks around and sees n people with blue eyes

If they each assume they themselves don’t have blue eyes, then, by the induction hypothesis, each blue-eyed person should expect that n other people will leave on night n

But on night n, no one leaves, which is a contradiction

Then their assumption is wrong, so they each conclude they themselves have blue
             eyes

Then on night n+1, n+1 (blue-eyed) people will leave the island

So P(n+1) follows

            Then ∀n∈ℕ | n ≥ 1, P(n) ⇒ P(n + 1)

Conclude ∀n∈ℕ | n ≥ 1, P(n)

With this proof, we can now answer the original question posed in the puzzle: all 100 blue-eyed people will leave the island, on night 100. No one else can logically leave.

Looking Back

            The answer the puzzle, based on the Inductive proof, is correct, although it may be a little difficult to swallow. I don’t think there are any other formal methods to go about answering something like this. If anyone has a clearer way of explaining this then let me know!

(Here is the xkcd solution: http://xkcd.com/solution.html)

Assigment 1 - Question 4, and the Psychology of Problem Solving Barriers

Right off the bat, I decided to do question 4 on assignment 1 with Complete Induction. It would be simple, really, just consider a sub-string of the string of binary digits from the 2nd to 2nd-last digit so the Induction Hypothesis could apply, and have a few cases to cover different first and last digits...or so I thought. Well into my proof I realized it was quickly becoming too complicated and would need rethinking, which brings me to two common barriers of problem solving identified in the world of Psychology - mental sets and (mental) fixations.

A mental set out of habit refers to the tendency to approach new problems only with previously successful methods or beliefs, and I've just been in a Complete Induction mode lately. Closely related is fixation, which occurs when you have latched onto a certain method, and results in an increased difficulty to see alternatives (like you needed psychology to tell you about that!). Many studies have shown the best way to overcome fixation is to take a break and distract yourself, a value that can't be afforded by someone working on the assignment the day it's due. 3 pages and 10 cases later, I couldn't help but think there was a better way to tackle question 4.

CSC236 - Introduction to the Theory of Blogging?

Hello everyone, and welcome to my SLOG for CSC236! The inspiration for the URL would be these wonderful words of wisdom on proofs from our former Prime Minster, Jean Cretien:

 

I've never blogged before, so I guess this course is an introduction to both blogging and the theory of computation for me! I personally don't quite see the point of keeping these SLOGs (hopefully that will change as mine progresses), but it seems easy enough.