100 people are in a room.
- All 100 of them are perfect logicians.
- They are told that at least one person in the room has blue paint on their forehead.
- They are told that once you deduce that you have blue paint on your forehead, the next time that the lights are turned off, leave the room.
All 100 people have actually had their foreheads painted blue (but of course, each of them don’t know this at this point – they can only see the other people’s foreheads). The light is turned off, then on, then off, on, etc. What happens?
Answer:
So each person sees 99 other people with blue paint on their heads. While this is the situation we begin with, it doesn’t seem to help with solving the problem at all. The key for this problem is to start as small as possible and then expand.
Start with 1 person. 1 person in a room sees 0 other people. Thus, if there is at least 1 person in the room with blue paint, he or she must be it. The light goes off, and then on, and we see 0 people in the room, as the person has left.
Let’s say we have 2 people. Put ourselves in to the shoes of one of them. They see 1 person in the room with blue paint on their forehead, and don’t now if there is blue paint on their own forehead. But if there was no blue paint on their forehead, then the other person should deduce that they must be the one with blue paint on their forehead, and will be gone by the next light. The light is turned off, then on. Since both people see the other person with blue paint, both remain. Now, each person knows that the other person looked at their forehead and saw blue paint, and so each person knows that they have blue paint on their own forehead. The lights turns off and on, and there are 0 people in the room.
I think you know where this is going (although I find the logic the most difficult from here). 3 people in the room. Each person sees 2 other people with blue paint on their foreheads. The additional key here is, each person needs to think, “What if I don’t have blue paint? If what happens then is a contradiction, then I must have blue paint.” Choosing one person’s perspective – our “first” person – we first posit that we don’t have blue paint. In that case, each of the other 2 people sees 1 person without blue paint and 1 person with blue paint. Our existence as someone without blue paint doesn’t matter in their calculations. Each of them thinks, “There is one other person in this room with blue paint. If they see me without blue paint as well, then they should disappear by the next light. The light turns off, then on. All 3 people are still there. So each of the other 2 people think, “Since that other person didn’t leave, I must have blue paint. So I will leave by the next light. The light turns off and on. But since the truth is that all 3 people have blue paint, the other 2 people won’t disappear. Instead, each of them are thinking the same thing about the other 2 people in the room that they see have blue paint on their foreheads. Everyone waited two turns to see if the other people would make a move. Since they didn’t, everyone has found a contradiction to “If I had blue paint,” and thus everyone deduces that they have blue paint on their own forehead. Thus, the third time that the light goes off and on, the 3 people have left the room.
4 people in the room. Assume you don’t have blue paint, so your being there doesn’t affect the others’ logic. There are 3 people wondering if they have blue paint and the each see 2 other people with blue paint. After 3 turns of the light going off and on, they should all leave. If they don’t, we have a contradiction, so we have blue paint. So on the 4th light, all 4 people leave.
5 people in the room. Described another way: Let’s say we don’t have blue paint. There are 4 other people with blue paint. Let’s label them A, B, C, and D. D is wondering if he or she has blue paint, looking at A, B, and C. D first assumes he has no paint and is thinking, “C is thinking if he doesn’t have blue paint, then after 2 turns, A and B will disappear.” After 2 turns, A and B remain. D is thinking, “So now, C will conclude that he has blue paint. So on the 3rd turn, A, B, and C should leave.” After the 3rd turn, A, B, and C remain. D is thinking, “OK, so there’s a contradiction to the assumption that I don’t have blue paint. Thus, I have blue paint, and will disappear on the 4th turn.” On the 4th turn, we see that A, B, C, and D still remain. Thus, we have a contradiction to our first assumption that we have no blue paint. We have blue paint, so on the 5th turn, we leave. Everyone else also has the same logic process, so on the 5th turn, everyone leaves.
If there are 100 people in the room, all with blue paint on their foreheads, first assume that you don’t have blue paint on your forehead. So then, your existence shouldn’t matter to the other 99 people’s logic. Let’s label us A. There are 100 people in the room: A, B, C, …, X, Y, Z, AA, AB, …, CV. Person A first assumes they have no paint, and thinks, “B must be thinking, if I don’t have paint, then, C would think, if I don’t have blue paint… etc.” Basically, we are testing the assumption that everyone first assumes that they themselves don’t have blue paint on their forehead. It doesn’t make intuitive sense since anyone can see that there are at least 99 other people with paint, but it’s the key step. Assume, what if everyone from A to CV thought that they didn’t have blue paint? Or rather that A assumes they don’t have blue paint and that B assumes that B doesn’t have blue paint and B assumes that … CU assumes CU doesn’t have blue paint and that CV assumes that they don’t have blue paint? Well, this is a contradiction, because at least 1 person must have blue paint. Now, let’s assume A to CU thinks that they don’t have blue paint and CU sees CV has blue paint and must assume that CV sees everyone else with no paint. After 1 turn, CV doesn’t leave (because it’s not true that the other 99 people don’t have blue paint), and thus we have a contradiction and CU must believe that they have blue paint on their forehead as well. After turn 2, CU doesn’t leave though (because it’s not true that the 98 other people other than CV and CU don’t have blue paint), so we have a contradiction and CT must believe that they have blue paint. Keep going until turn 99, where B doesn’t leave because it’s not true that A doesn’t have blue paint (if B saw that A doesn’t have blue paint, B should have left on turn 99). We have a contradiction, so A concludes that they have blue paint, and so on turn 100, everyone leaves.
It’s a lot easier to rely on the formula we built from the smaller examples that “With a room of x people, they all leave at once after x turns.” But I find the intuition disappears with large numbers. The above paragraph is an attempt to describe the intuition, the key being that we assume that all x people assume that they don’t have blue paint, and then one by one contradict that (because in reality, everyone has blue paint), until we’ve contradicted all cases down to 1 person assuming they have no paint. Once that is contradicted on the xth turn, after that, everyone leaves at once, since everyone has the same logic process.