The Blue Forehead Room Problem

[Jonnyb42]

Summary is below, here are the original videos.
(Also, in case this problem has been posted before, you can show me the link, I could not find it.)

The Original Problem: http://www.youtube.com/watch?v=rBaCDC52NOY"

The Solution: http://www.youtube.com/watch?v=-xYkTJFbuM0"
(I have a problem with this solution which I will explain.)

In case you don't want to watch all of it here is my summary:
100 perfect logicians are in a room, each knows:
There are 99 others.
At least 1 of them has had their forehead previous painted blue.
(Each doesn't know if they are blue or not.)
Scenario:
They enter the room in the dark. Then the lights turn on, they make deductions but cannot communicate with each other. Then the lights go off, and those that fully deduced that they are painted blue leave. The lights turn back on, they do more deducing, and the the lights go off and the process repeats.

Now the question is:
If they are all painted blue, what happens?

I don't have a summary for the solution, you will have to watch the video for that.
Without the explanation, the simple answer is:

Spoiler

All of them will leave together on the 100th night.

It makes sense, but there is a problem when thought about differently:

Spoiler

Since everyone knows that everyone can see at least one blue, everyone knows that (everyone else knows) nobody will leave the first night. Therefore, (it is an open fact) no information is gained by each person after the first night. Any remaining nights must be the same, so nobody will ever know for sure if they are blue or not.

What I think the answer is:

Spoiler

They would stay there forever. 4 number of people and up makes it impossible to tell.

I understand both ways, but both ways have different results, leaving me confused.

What do you guys think?

 

[1MileCrash]

I agree with the video solution.

 

[Jonnyb42]

I agree with the video solution.

Well what do you think of what I said.

 

[Four]

I also agree with the video. I have heard a more cruel version of this. It just becomes difficult to think about without paper. Its deductive, at 4 and up its just not too easy to think all in your head.

 

[apeiron]

reposting as this is the better home for the thread it seems...
---------------------------------------------------------------

Thanks, a fun teaser.

The problem with your option 2 is that the people would not be making full use of the information available to them as required.

They can see everyone else is blue, and so only their own situation is uncertain. Consider how different this is from the other extreme where only one head is painted blue (and you can't see anyone else, so you must leave immediately).

If there was then some mixed state, that would again be informational. So imagine four in the room and you can see two blues and one non-blue. You can eliminate the non-blue guy as a walker because he is one step more uncertain than anyone else (for him, there could be four blues in the room, where everyone else knows it is a maximum of three).

So now you wait to see if the two blues react on the basis that you are blue too (so adding another turn) or whether they see you as a second non-blue and so a second non-walker, leaving them just watching each other's response.

So a room of all blue in fact tells you something different than some other mix of blues and non-blues. And the requirement is to take account of this information.

Of course, a Bayesian logician would be out the first round if he found himself in a room where everyone else was blue.

 

[Jonnyb42]

But what information can possible be obtained after the first night?

 

[apeiron]

But what information can possible be obtained after the first night?

That you too have not yet been eliminated from other people's calculations.

Take again the mixed example of four in a room that is divided 2B, 1NB and ? (which is you). This means either the room is actually 3B or 2B. And so you know there are two others who parse the room with the same view you have, and a third who is thinking in terms of one extra possibility - the room could be 4B as well as also either 3B or 2B.

The 4B guy can't walk ahead of any of the 3Bers. He cannot see a reason. So that narrows the action during the next few rounds.

If the other guys are then actually seeing a 2B room, they must have discounted you on the same grounds, and so will have to walk before you walk. And when they don't, then all three can jointly know it was a 3B room.

 

[Jonnyb42]

Yeah, but how does the process work when you see 3 other blues, (and you yourself are blue.)

 

[apeiron]

Yeah, but how does the process work when you see 3 other blues, (and you yourself are blue.)

As the video would describe. You know that either you are all equal in your probability of walking and so require the same number of turns, or the other three have information to discount you already and will be calculating events on that basis, which requires one less turn for them. The only way to find out which is the story is to wait the right number of turns.

 

[1MileCrash]

But what information can possible be obtained after the first night?

Essentially that, those with blue foreheads come to the same calculation as you regarding others with observably blue foreheads.

Easier to see it from an 'objective' viewpoint.

 

[Jimmy Snyder]

Imagine there are only two people in the room. You and another. If you see his forehead is not blue, then since at least one forehead is blue, it must be yours and so you leave. By the same reasoning, if he sees that your forehead is not blue, he leaves. But if you see his forehead is blue, then you don't know if you can leave. The same goes for him, he doesn't know if he can leave, so he stays. The fact that he stays tells you that he saw your forehead was blue so you can leave. By symmetry, he can leave too. The same reasoning works for three people. If, on the first pass you saw two nonblues, you would leave. Since you saw two blues, you didn't leave. Now they know you saw at least one blue and they see your blue for two blues. If at this point someone saw a nonblue, they would know that theirs is one of the two blues and would leave. Since no one leaves, that means that no one saw a nonblue and so all three are known to be blue and so everyone leaves. Etc.

 

[Hiiiaiiei]

According to Sal's Solution: if there are n blue people they will all leave on the nth night.
This is incorrect for all n's greater than 3. I'll show you the reasoning why. Assuming Sal's Solution to be Correct with n people leaving on the nth night: if you have 100 blue people.
If this solution is correct. All the "Perfect Logicians" would know this to be "true" as well. So if one person in the group of 100 blue people will see 99 blue people and not be sure what he is. So that guy who sees 99 people knows that everybody else can see at least 98 blue people. This is because person 1 doesn't know his color, so he can't assume that the second guy sees 99 blues. Person 1 knows that person 2 can see at least 98 blues. persone 1 also knows that person 3 can see at least 98 blues. and so on and so forth. so person 1 knows that he can see 99 and person 1 knows that everyone else can see at least 98. So everyone knows that since the number of blue people is at least 98,(according to the "Correct solution" (Sal's solution)) that it will take at least 98 nights before anyone can leave. because everybody knows that everybody knows that n equals at least 98. So why would anyone wait for 100 nights if they know nothing is going to happen until the 98th? they shouldn't wait. they would shift the "98th night" to be the first night, the "99th night" to be the second night, and to be the "100th night"

If there are n blue people, there is no reason for them all to stay for n "days" (when the lights on).
The MAXIMUM "nights"(when light is off) any number will every need is 3.
The only reason why this is the case, is because everybody is a perfect logician and everybody knows that everyone else is a perfect logician.

 

[Hiiiaiiei]

I realize, that my thinking is off, and i have now realized i could probably definitely be wrong.

 

[dgitting]

For a moment, disregard the fact that all 100 know that there can be no more than one blank forehead, since they’re all looking at 99 blue ones.

• Simply consider this. We all know that we all know that there are at least 98 blue foreheads. Why? Suppose you are among the 100. You cannot name one person of the other 99 who does NOT know that you see 98 blue foreheads, the same 98 that he sees in addition to yours.

• If there are TWO blank foreheads, then the other 98 would see those two blank foreheads and only 97 blue foreheads.

• Thus, because we know that we all see 98 blue foreheads there cannot be two blank foreheads.

• Thus, if anyone sees ONE blank forehead, he or she will know it’s the only one and leave the room the second time the lights come on.

• Hence, if my forehead is blank, everyone would leave.

• But no one leaves, so no one sees any blank forehead.

• So we all leave the third time the lights come on.

For simplicity, consider the case where there are only a few people involved, say 6, all of whom have blue foreheads. When the lights come on the first time, we all can tell that each of us sees at least 4 blue foreheads. If there were TWO blank foreheads, then 4 people would see 2 blanks and 3 blues, but we know they see 4 blues. That eliminates the possibility of two blanks. Hence, if anyone sees a blank, it must be the only one. Since no one leaves the second time the lights come on, no one sees a blank forehead. The third time the lights come on, we all leave.

Dennis Gittinger

 

[Parlyne]

• Simply consider this. We all know that we all know that there are at least 98 blue foreheads. Why? Suppose you are among the 100. You cannot name one person of the other 99 who does NOT know that you see 98 blue foreheads, the same 98 that he sees in addition to yours.

This is simply not correct. It presupposes the knowledge that you have a blue dot on your head. If you don't assume this, then it can't be the case that everyone knows that everyone knows that there are at least 98 blue foreheads.

Consider breaking it up into cases. If your forehead is blue, then each person sees 99 blue foreheads and, thus knows that each other person must see at least 98.

However, if your forehead is not blue, each other person sees only 98 blue foreheads and, thus, only knows that each person other than you sees at least 97 foreheads.

Since you don't know whether or not there's a blue dot on your forehead, you don't know which of these cases holds. Therefore, you only know for certain that each other person knows that there are at least 97 blue foreheads.

But, it gets worse because the ability in your solution to leave after a small number of nights not only required that you know about other peoples' knowledge, but that they know about each others.

So, consider the perspective of another person in the case where you do not have a blue dot. That person sees 98 dots; but, not knowing whether he has a dot himself can only conclude that each other person (other than you) sees at least 97 dots and, thus, that that person, in seeing 97 dots, can only conclude that each other person must see at least 96 dots. And, we can continue on in this manner.

The point is that we must consider what the knowledge of the other observers would be in the (counterfactual) case where we do not have a dot. And, we must consider in looking at that knowledge that each other person cannot discount their own counterfactual case.

 

[Youler]

I found it easiest to think of this problem as a bunch of nested assumptions. For instance in the 2 person case you assume that you are not blue (NB) and wait for the 2nd night to see if the other person has acted. In the 3 person case, first assume you are NB. Choose another person (AP). AP must also assume that he is NB and wait for the third person to act. When nothing happens he would know that his assumption was incorrect and leave. When this does not happen you know your assumption was wrong and so you leave. The problem is symmetric so everyone in fact leaves.

Now I will try to extend this to 4 people and apologise in advance if it is unclear.

1) Assume you are NB
2) AP assumes that he is NB, thus 2 people are NB
3) Another another person AAP assumes he is NB. (thus 3 NB people)
-The fourth person would leave. This doesn't happen.
Assumption 3 was wrong.
If assumption 2) was right then AAP would leave (with the fourth person - sym).
This does not happen so Assumption 2) is incorrect. So everyone else would then leave if you were NB. This does not happen so assumption 1) is incorrect.
Everyone now leaves (due to symmetry).

Sorry if this got incoherent.

 

[Youler]

I've had a think about it and think i can explain the 4 person case in a clearer way.
I will be person 1 (P1), there are 3 other people P2, P3 and P4. T

Assume my forehead is not blue. (Assumption 1)
P2 assumes his forehead is not blue. (Assumption 2) He then looks at P3. If his assumption was correct P3 would be in a room with 2 not blue and 1 blue. P3 then assumes that his forehead is not blue. (Assumption 3) P4 would then see 3 not blue people and leave after the 1st night.
This does not happen.

The assumptions are nested. By that I mean assumption 3 relies on assumption 2 being made which in turn relies on assumption 1 being made so we must take them in order.

Since P4 did not leave assumption 3 is incorrect. So P3 would know (in P2's mind) his forehead is blue and he and P4 would leave on the 2nd night (both for the same reason). This does not happen so assumption 2 is wrong.

Repeat this for assumption 1.

This is easily generalised for n people.

 

[Youler]

Much nicer explanation here...
http://richardwiseman.wordpress.com/2011/04/04/answer-to-the-friday-puzzle-98/

 

[AJPeterson49]

This brain teaster was very enjoyable however I believe the solution is incorrect. In the example posted by Youler, for the 4 person case, I believe that there is an error in logic, specifically: P2 cannot assume that P1 is not blue since he knows for a fact that P1 is blue. For P2 to assume that P1 is not blue is illogical and would make P2 an imperfect logician. The solution only works for 1, 2, or 3 blue foreheaded people. For 4 or more blue foreheaded people, nobody should leave the room, no matter how many times you turn thr lights on and off... although I do like Apeiron's suggested use of Bayesian logic where everyone leaves immediately on round one.

 

[Parlyne]

You are misunderstanding. In the analysis, P2 never makes assumptions about P1. The entire discussion subject to assumptions being made by P1. To wit, P1 must consider what behavior he expects from the others in the room if he has a dot and what behavior he expects from them if he does not have one. That's where the assumption comes in. P2 clearly knows the state of P1's head. In fact, P1 knows that P2 has that knowledge; however, P1 doesn't know what the content of that knowledge is, which is why he has to break it down into cases. (In fact, if P1 knew that P2 knew that P1's head was blue, then P1 would already know that his own head was blue.)

 

[thil999]

This is how i explained it to myself and hope it helps.

Everyone agrees that 2 and 3 people in a room, its possible to deduce. Now if it can be proven to 4 people, then we can safely deduce the pattern will hold for any number of people.

B=Blue and NB=Non Blue.
P1 = Person 1 P2= Person 2 and P3=Person 3 and I am the last person in the room.

Scenario 1 - 3 person are NB and 1 is B

If I see 3 NB, I know I am Blue and leave on 1st round.

So after 1st round, 1 leaves if there are 3NB in the room is a fact.

Scenario 2 - 2 person are NB and 2 are B

If I see 2NB and 1B I will wait for the person who is blue to leave on the 1st round if he is experiencing situation 1(which is 3 NB). Since he does not leave, I will leave on the 2nd round since i know i am blue through deduction. Same logic applies to him as he sees 2NB and 1B just like me.

So the fact is, if the person is blue, he will leave on 2nd round if there are 2NB and 2B. So 2 people leave.

Scenario 3 - 1 person is NB and 3 are B

If I see 1NB and 2B, it is possible for the 2 people who are blue to see 2NB and 1B if I am NB. Hence they will be in scenario 2 and will leave after 2nd round. Since they both do not leave after the 2nd round, I will leave on the 3rd round as I will know I am blue. Same logic applies to the other 2 as all of us are in the scenario of seeing 1NB and 2B.

So the fact is, if the person is blue, he will leave on the 3rd round if there are 1NB and 3B. So 3 people leave on the 3rd round.

Scenario 4 - 4 are B

2 possibilities. 1- I am NB. If i am NB, then the scenario is 3. So 3 people will leave after 3 rounds.

2nd possibility - I am B. I know I am B if nobody leaves after the 3rd round. So i will leave on the 4th. So will everyone because everyone sees 3B.

Hence 4B will take 4 rounds for everyone to exit. Now applyin this logic, 100 people = 100 rounds :)