Monty Hall Problem

I would imagine most people who would bother reading a blog like this are very familiar with the Monty Hall problem. Of course, in the interest of completeness, I'm going to state the problem here:
You are on a game show where you must choose between three doors. Behind one door is a prize, and the other two doors have nothing behind them. After you select a door the show host, Monty, will open one of the doors that has nothing behind it. Monty, of course, knows exactly where the prize is and is always able to select such a door. You are then given the option to select a new door. What is the optimal strategy to select the door with the prize?

Given a bit of analysis, its not too hard to determine the optimal solution, though some people have a hard time wrapping their minds around it. However, opponents of the standard solution often point out an unstated assumption, and that is that Monty will always offer you the choice to switch. If Monty gets paid based on contestants not finding the prize, then perhaps Monty would rather only offer the switch to contestants who correctly guessed the prize door. In this case, it is clear to see that you should never switch. Of course, perhaps Monty will occasionally offer the switch to a contestant who is wrong, just to mess things up a bit.

After thinking about this, I came up with a extension problem to work out:
Suppose Monty will offer the switch with probability x to a contestant who picked the right door, and will offer the switch with probability y to a contestant who picked the wrong door. Assuming the contestant watches the show frequently enough to determine the values of x and y, what is the optimal solution for the contestant? What are the optimal values of x and y for Monty?

If you feel like working this out yourself, I encourage it. Its not a particularly hard problem, and the answer is very intuitive.

Anyway, I'm going to post the answer here now.

Suppose the contestant decides he will accept the switch with probability c. c cannot depend on the contestant getting the right door, as the contestant doesn't know, however, c can depend on x and y.

The probability the contestant wins is given by the sum of two terms. First, the probability they got the wrong door (2/3), times the probability of being offered the switch (y), times the probability they accepted the switch (c). The second term is in two pieces, the probability they got the right door (1/3) times the probability they were not offered the switch (1-x), and the probability they got the right door (1/3), were offered the switch (x), and refused it (1-c).

Adding it up, the probability the contestant wins is given by:
P=1/3(2yc+(1-x)+x(1-c))

P=c/3(2y-x)+1/3

Since this is just a linear function of c, it will be maximized at the endpoints, either c=0 or c=1, depending on if 2y-x is positive. If Monty offers "good switches" (y) more than half as often as he offers "bad switches" (x), then you should switch, otherwise don't. If 2y-x=0, then either switch or do not, it doesn't matter.

The optimal solution for Monty is to make sure 2y-x is not positive, because he has no way to reduce P less than 1/3 (the contestant can always choose c=0), but if 2y-x is positive then P will be greater than 1/3 with c>0.

Finally, note that in the original case, if Monty always offers the switch then x=y=1, and the optimal solution is to switch. c=1 gives that P=2/3, whereas never switching gives P=1/3. So this method also solves the original Monty Hall problem.

Logical And Wrong

So, continuing my last post about monks with eyes, (though I should start calling them islanders now), if everybody assumes that their eye colour is one they have seen before, then they actually can figure out stuff fairly quickly. Its interesting to see what happens if that information is wrong though.

For example, assume there is 1 blue-eyed person and 3 brown-eyed people. The blue-eyed one will have to assume his eyes are brown and leave that night, and the brown eyed people will figure out it the next night and leave. Of course, the blue-eyed person will leave because he thought he figured out his eyes were brown and he is just wrong, but thats what happens when perfectly logical people are told the wrong information.

Continuing upward, if there is 3 blue and 2 brown, the 2 brown leave on the second night and the blue leave on the third night, its easy to see this because a brown eyed person will assume his eyes are either brown or blue.

Next, assuming there is 1 green, 2 blue, and 2 brown, the green-eyed person will assume his eyes are either blue or brown. If his eyes are blue, the brown eyed people will leave on the second night and vice-versa for brown. When the second night comes and nobody leaves, the green eyed person must realize a contradiction.

At this point, you can't really guess what happens next, when perfectly logical people see a contradiction they might come to second guess everything, so we really have no choice to declare there is a contradiction and end there. As a side note, the blue and brown eyed people all know that somebody has seen a contradiction, but they cannot figure out who knows it.

After seeing this, I came to a conjecture:
Either somebody will realize there is a contradiction and nobody leaves, or everybody will eventually leave the island.

Its not hard to justify this, as if anybody leaves, then everybody else gains a big piece of information, but if a contradiction is seen and somebody doesn't leave in time, then nobody can gain that information (unless, I suppose, if the person who found the contradiction is allowed to announce it).

Last neat thing I want to say about this puzzle is what happens if you give the assumption that no person has a unique eye colour. This is slightly different than the assumption that each person has an eye colour they have seen before (in spite of the fact that both are true under the same circumstances, which still sort of confuses me a tiny bit, to be honest).

In this case, with 2 brown and 2 green, they all leave on the first night, seeing that they all can see an eye colour that only one other person has. And with 1 blue, 3 brown, and 3 green, the brown and green will assume their eyes are blue the first night, and will all leave, and the blue guy will simply be left asking where everybody went. It appears my conjecture does not hold here anymore.

Alright, I'm done with that class of monk problems (for now). I'll start something new next time.

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.

Monks With Hats

Usually, after solving a logic problem, I like to take some sort of generalization of it just to complicate the issue. A typical example of that is to take a problem that only applies to natural numbers and solve it assuming its parameters can take on real values. This process isn't always very well defined, but I am usually pleased with the result anyway. Before I can start that though, I suppose I'll introduce the logic problem that triggered me to actually start this blog. I first learned this problem from Bart.

Consider a monastery with many hat-wearing monks in it. The hats can be either white or black, and the monks have taken vows not to look at their own hat or point out others hats or stuff like that (standard hat rules apply). Further, the monks have taken a vow that any monk who discovers their own hat colour is to kill themselves at midnight that night. When a monk dies this way, all the other monks are aware of it the next day. Finally, all the monks are perfectly logical and are all aware of all information in this paragraph.

Let us assume for definiteness that there are 50 monks, 25 with black hats and 25 with white hats. One day a rabbi, who does not particularly like these crazy hat-wearing monks, comes by to speak with the monks. He gathers all the monks together and announces to them, "I see that at least one of you is wearing a white hat today." The rabbi then leaves the monastery, what is the fate of the monks?


If you think the answer is "they happily live out many years of life", I should tell you the easier version of the problem where I end off the problem by saying this: Two months later the rabbi returns to the monastery, and all the monks are dead. On which day did the monks die (specifically, for each monk, on which day did that monk die)?

I won't state the solution in this post, just because some people might not want it spoiled for them, so I'll give it a day before making the next post.

Who Blogs These Days?

Apparently, these days anybody can be tricked into starting a blog, even me. One has to wonder what percentage of blogs actually get read by people outside of the bloggers circle of friends, but I suppose thats no reason to not blog. The main advantage of blogging is that you don't have to notice just how much people do not want to hear your random ramblings on things. If somebody doesn't care about what you write, they just stop reading, and you just keep writing anyway.

I suppose for my first real post though, I might as well explain what the title is about, just in the off chance that people outside of my circle of friends do actually read this thing. Simply put, I spend far too much of my time working on logic puzzles that begin with something like, "Seven people are in a room, and they are all wearing hats of various colours. Each person can see eachothers hats, but they cannot see their own through any means, nor can they communicate their hat colours to eachother in any way," but because so many problems involving hats have that last bit about not being able to see your own hat, but being able to see all the other hats, it helps to shorten that to just saying "Standard hat rules apply."

Yep, thats all I got.