Monks With Eyes

So, given that nobody is actually reading this blog yet, its not 100% clear why I would wait for a day to post the solution to my monks with hats problem. Really, the reason is that I am worried that I only have a finite amount of blogging material, and I really don't want to waste it right away. As a general warning, there are spoilers ahead, so if you actually wanted to solve that problem yourself (and you know you want to), now would be the time to stop reading this.

Alright, to solution is simply that after 25 nights, the white hatted monks all kill themselves, and after 26 nights, the black hatted monks do. This can be most easily seen by considering a case where there is one monk of each hat colour, then moving up to two, and so on upwards until you are ready to prove by induction. Of course, no matter how much you think about it at first, pretty much anybody spends a long time being tripped up by this puzzle before they really come to accept it.

It is quite interesting to ponder what exactly it was that the rabbi told the monks that they did not already know, and if you can answer that, you will probably be more at peace with the answer (at least thats how I got to be).

An variation of this puzzle, which I first learned from xkcd, is that there is are a bunch of islanders who must leave the island at midnight if they learn their own eye colour. Suppose the island has 50 people with blue eyes, and 50 people with brown eyes. Then one day somebody comes along and points out that at least one of them has blue eyes.

Clearly this problem is the same as the monks with hats problem, so 50 nights later the blue-eyed islanders leave, followed the next night by all the brown eyed ones.

"But wait", the more pedantic of you will say, "there is no limitation on eye colour to be blue or brown, any of the brown eyed people can just assume they have green eyes and all is well." You would, of course, be quite right to say this, and so one can come up with a neat variation of the puzzle by adding one more assumption.

All of the islanders will assume that their eye colour is an eye colour that they have seen somebody else on the island have. Specifically, if you have only ever seen blue eyes or brown eyes, you will assume that you must have either blue eyes or brown eyes. Also, it is common knowledge that everybody will operate under this assumption.

As I was thinking about this one day though, I realized that something funny can now happen. If there is 50 blue-eyed people and only 2 brown-eyed people, then the brown-eyed people will say "If I have blue eyes, then that brown-eyed fellow will assume his eyes must be blue and leave tonight." Then of course when he stays, both brown eyed people will figure out their eye colour and leave that night. The next night the blue-eyed people will figure out that the only way the brown eyed pair figured it out would be if they had blue eyes, and so they all leave the third night.

Turns out nobody had to come along and give these islanders extra information, they will leave all by themselves. I suppose this problem is not quite as well posed at the other one, but there are some funny things that can happen with it. More about that next time.

No comments: