Exercises in probability & strategy

Here are two classic problems where you need to use your knowledge of probability theory and general logic respectively. Lots of you have probably heard one or both before, but maybe there's someone out there who hasn't.


1) You are at a game show where you have the chance to win a brand new BMW. In front of you are three closed boxes. One of them contains a car key, and the other two are empty. If you pick the one with the key, you get the car, otherwise you get nothing.


First you are asked to pick one of the boxes. The game show host knows where the key is and he will remove one of the empty boxes, but not the one you have chosen even if it's empty. (You have no tell on him, and he is honest, there is no trick here). Then you will be asked to decide whether to stick with your initial choice, or to switch to the other box. What should you do?


2) The emperor of China is in the process of hiring a new counsellor. He wants the brightest man in the empire (after the emperor himself, presumably). After a long and thorough search he is down to three candidates. They are all extremely bright and able, but only one of them can get the job.


The three candidates are asked to sit down at a table on which there are five hats; three black and two white. They are instructed that they will be blind folded, and each have one of the hats put on their heads. The remaining hats will be taken away, so they cannot be seen. The blind folds will then be removed and the candidates' task is to decide upon the color of their own hat. They cannot see their own hats, only those of the other two candidates. Guessing is not allowed, and the one who claims to know the color must explain how it was concluded. The first one that gets it right will be chosen as the emperor's new counsellor.


The candidates are blind folded. Each of them gets a black hat, and the two white hats are taken away. The blind folds are removed and after a short while one of the candidates says "I have a black hat". How did he know this?


I claim that there are two different, but closely related, explanations to this problem. The classic (or at least I believe it is the classic) involves some uncertainty, while the one I prefer does not. At least not the same kind of uncertainty.


I will soon present answers to both problems, but I give you some time to think about it first.

Keep your initial choice. but I'll let the others elaborate.


2ndGoat

Correct answer to the "Monty Hall" problem is to switch.


Here's why. You've got 1 chance in three (2:1 against) of having made the right choice. Monty, *knowing the correct answer*, opens a door of his choosing, revealing an empty room.


The contents of your choice haven't changed, so it's still a 2:1 dog to be the correct choice. But there remain two unopened doors, one of which contains the prize. Therefore, the other door is a 2:1 *favorite* to contain the prize, since the sum of the probabilities of all outcomes must add up to 1.


Don't believe it? Look at the case where there are 100 doors, not three. You pick one, you're a 99:1 dog to have chosen the prize. Monty, knowing which door contains the prize, opens 98 doors and reveals that they contain nothing. The prize is behind one of the two doors. You chose your door when the odds were 99:1 against your picking the prize. The content of your choice hasn't changed. Monty, *knowing where the prize is and deliberately choosing not to open the door containing the prize*, revealed 98 empties. The prize is behind one of two doors. There's a 1% chance it's behind your door, and a 99% chance it's behind the other door. Are you going to switch?

Alan Bostick is correct. An equivalent explanation, only put in other words follows:


There are three strategies that seem reasonable before having analyzed the problem:


1) Choose randomly between the two. Since there is one empty box and one with the key, you'll get a 50% chance of winning the car.


2) Don't switch. The probability of having picked an empty box is 2/3 and of having picked the key is 1/3. The conditional probability of winning if you started with an empty box is 0 and if you started with the key it is 1. Therefore the probability of winning is 2/3*0+1/3*1=1/3.


3) Switch. The probability of having picked an empty box is 2/3 and of having picked the key is 1/3. The conditional probability of winning if you started with an empty box is 1 and if you started with the key it is 0. Therefore the probablitiy of winning is 2/3*1+1/3*0=2/3.


This is a good exercise in conditional probabilities.

1 comes up periodically on forums like this, and the thread always explodes with posts. Let's see if I can prevent that this time around...


1. Obviously switch. Initially you will pick the right box 1/3 of the time, and if you don't switch that's how often you will end up being right. But if you switch, that 1/3 of the time that you were right will now become wrong as you switch away the car. But the 2/3 of the time you would have been wrong now become right, so now you are right 2/3 of the time.


2. I haven't seen this variation. Everyone realizes there cannot be 2 white hats, since otherwise the man with the black hat would see the two white hats and speak up immediately that his hat must be black. The wise man looks and sees two black hats, and he realizes that if his hat were white, each of the other men would see 1 white hat and one black hat, and thus conclude their hat must be black since cannot be 2 white hats. Since they do not speak up after sufficient time, he concludes his hat must be black. Of course this assumes the men think at the level the wise man gives them credit for. They can't think at the same level or they would have answered before him.


3. A variation of 2. In a village with no mirrors, some of the people have a disease, but since this village has no mirrors, they can only see the disease in others, not in themselves. The people also cannot communicate with each other to tell each other they have the disease. Each person with the disease is committed to killing themselves by midnight of the day on which they first realize they have the disease. How many days should it take to rid the town of the disease?


4. This one will drive you crazy. An announcement is made that next week there will be a surprise fire drill. The drill will occur at 3 PM on one of the days Mon-Fri, but no one will know ahead of time which day on which it will occur. You reason that it cannot occur on Friday and meet these conditions, since when doesn't occur by Thursday at 3 you will know it must happen on Friday. But then it can't occur on Thursday either since when it doesn't occur by Wednesday at 3 you would know it must occur on Thursday since Friday is ruled out. By similar reasoning we can rule out all of the days. So you conclude it can't occur at all and be a surprise when it happens. But of course on one of the days it rings out promptly at 3 and you are surprised. What was wrong with our reasoning?

3. They'll never be rid of the disease.


4. You only gain the knowledge of when the firedrill is to occur after it doesn't occur on the given day. Hense, if it doesn't ring on thursday, you would know it must occur on friday, but if it does ring on thursday, you're still surprised, because you don't know if it's going to occur today or tomorrow until after it does or doesn't ring.

Completely right... I withdraw my assertion. I "knew" the answer but didn't work it out in my head again before posting. gah. Question straight out of a textbook from this semester.


2ndGoat

...which is that each day, the people of the village are informed as to whether or not the disease has been eliminated. With this addition, the people of the village, who are all extremely intelligent, can eventually rid themselves of the disease. How can they do this and how long will it take?


Since I left out an important part of this problem, I will wait until tomorrow to post the answer to this as well as to number 4.


As I stated previously, each person can see who else has the disease, but no person can look in a mirror and see that they themseves have the disease, or be told by others that they have the disease.

one day


the first day they nominate someone without the disease to tell the ones who haven't got the disease they haven't got the disease


all the ones who are not told they haven't got the disease kill themselves by midnight

They can't communicate with each other at all as the original post says, so they can't tell someone they have the disease or that they don't have the disease.

The classic solution to the problem is the one that BruceZ gives above. I.e. the candidate reasons like this: Suppose I have a white hat. Then the other two see one white and one black. Each of these two must reason like this: "I see one black and one white hat. Since the guy with the black hat didn't immediately say his hat was black, mine must be black also." When the candidate realizes that none of the others has come to that conclusion he knows his assumption was wrong, therefore he knows he has a black hat.


The problem here is the timing. The reasoning goes in two steps. You must allow the others to complete the first step of reasoning, and you must answer before they complete the second step. There is no way to know when the time is right.


Therefore I give my solution to the problem. It demands that you have done the first two steps of reasoning, and then add the following:


If two white hats are used, then the one with the black will get a maximum advantage and win without contest.


If one white hat is used, then the one with the white hat cannot conclude that his hat is white. The contest is only between the other two.


Since the emperor obviously is wise, and he has arranged this test in order to find the best candidate, he cannot have decided that one or two white hats should be used. Therefore everyone must have been given a black hat.


This means that the candidate who reasons like this can speak up as soon as the blind folds come off, or whenever you are first allowed to give your answer. It is not necessary to guess when the right time is.

Every day at noon the citizens gather in the town center. They know at least one person has the disease. So if someone sees only healthy people he knows he has it and will kill himself by midnight and the disease is gone.


If the next day comes and nothing has happened they know at least two people are diseased. So anyone who sees only one diseased person will kill himself by midnight.


If the disease is still not gone the next day, they know at least three people have it, and anyone who sees two other will kill themselves by midnight.


And so on. On the last day everyone with the disease will kill themselves.

i think the answer is probably that village will be clear by the end of the third day - by trying simple cases it seems that you have one day without death and then all the diseased ones top themselves next day or the day after by midnight


for example using Da,Db, Dc, etc for diseased individuals and Ca, Cb, Cc, etc for Clear and neglecting the case when everyone in the village is infected at the start then imagine populations of two, three, and four, as simple cases


Da, Ca.... when told that day that village not clear Da knows its him so he tops himself


Da,Db,Ca... on first day nothing will happen - on second day both Ds will know they are D's because if either had been a C the other would have known on the first day - he would have seen two Cs


Da,C,C... D knows straight away


Da, C,C,C... D knows straight away


Da,Db,Ca,Cb.... Da can see DCC - he reasons that if he is a C then Db will be looking at CCC and will do himself in - he waits - Db behaves like Da for the same reason - meanwhile Ca can see DDC and he reasons that if HE is C then Da will behave as above so he waits as does Cb for the same reason - when no one dies that first day Da realises that he must be D as Does Db and they top themselves - Ca needs to wait another day to confirm the scenario as does Cb who then celibrate their disease free status on the third day


Da, Db, Dc, Ca.........Da can see D,D,C and will await events like Cb did on previous scenario - Da should reason that if he is a C then each of Db and Dc will separately know they are not a C when the other does not kill themselves on the first day and they will kill themseves on the second day - so he will hang on till the third day and then be given the bad news - but meantime the other two Ds will reason the same way as Da so they will also wait and then all three will top themselves on the third day, because that is the only possible scenario - ie if the other pair have not topped themselves then each cannot be C after all


if you can be arsed try 5's and 6's etc but the essence seems to be that ALL the D's top themselves at the same time in every case

3. Raoul has the right solution. This is a great problem because it appears that, under the stated conditions, there should be no way in hell the people can ever realize they have the disease. The solution is an example of the logical principle known as mathematical induction.


The axiom of induction states that if a statement is true for some integer n = N, and IF it is true for some n THEN it is also true for n+1, then it is true for all n >= N. Think about this if it's not clear. It's an AXIOM of logic meaning that it is not something which can be proven; it is taken as a self-evident given which provides a basis for logical thought.


In this case we know it is true that when 1 person has the disease on day 1, that person will kill himself. In general we know that if N people will kill themselves on day N, then N+1 people will kill themselves on day N+1. Therefore no matter how many people n have the disease, they will all kill themselves on day n.


4. (fire drill problem). The lack of responses to this problem may indicate that many people missed the point of why this is even interesting. If so, think about if we can rule out Friday (since then we won't be surprised anymore) so the original problem can be recast as "the bell will ring Mon-Thurs". Then you can see the problem here...all the days can be ruled out.


All logical arguments must be based on 4 fundamental principles or axioms which follow. Here, A and B are statements, A => B means "A implies B".


1. If A = B, then A => B (equivalence...pretty obvious).


2. If A => B and B => C then A => C (deduction)


3. If A => B and NOT B, then NOT A (contrapositive). Example: If it were raining, we would be wet. We are not wet, therefore it is not raining. This is the well known proof by contradiction. You assume the opposite of what you are trying to prove, and find this leads to a false statement, therefore what you really wanted to prove must be true. Believe it or not, as powerful and self-evident as this axiom is, there is a school of logicians who have major objections to including this in the set of axioms for reasons of their own (maybe because of problems like the fire drill problem I'm not sure). The rest of us use it all the time.


4. If A1,A2....An are statements, and if A1 is true, and if An => An+1, then all An are true. (induction, see question 3 above).


In the fire drill problem, we are trying to use axiom 3 to prove the bell can't ring on Friday. We say, IF the bell doesn't ring until Friday, then on Thrusday we will be able to deduce that it will ring on Friday. But the conditions of the problem state that we will not be able to deduce in advance when it will ring, a contradiction. Therefore it can't ring on Friday. This statement "we would be able to deduce on Thursday" is at the crux of the problem. The accepted solution to this problem is that we have no basis for such a statment, that this business of deducing that in the future based on conditions that we do not yet know will occur, that we will be able to deduce something else, is faulty. Indeed, if we accept as given that we will NOT be able to deduce when it will ring from the problem statement, then this line of reasoning leads us to conclude that the bell can't ring at all, a violation of the other condition. Thus our process of deduction fails to make the original problem statment self-consistent, and yet this very failure of deduction causes us to be surprised when the bell does in fact ring out.


A paradox differs from a fallacy in that a fallacy has its basis in a clearly identifiable (though not always obvious) logical or mathematical error. A paradox depends on something more fundamental to the underlying subject, often having to be decided arbitrarily by the introduction of some new axiom. If the explanation above is not entirely satisfactory to you, it is not entirely satisfactory to me either. I believe that this problem presents something close to a true paradox of logic.