You label my back; I'll label yours

March 2004

You label my back; I'll label yours

basket of labels

A group of N friends go into a mirrorless room, in which there is a basket containing labels, each of which is either blue or yellow. None of the friends knows how many of the labels are blue or yellow - the labels may even be all blue, or all yellow.

Each person takes a label from the basket without looking and sticks it on his or her own back. When everyone has done this, they all circulate freely and soon everyone knows the colour of everyone else's labels, but still does not know the colour of their own.

Another person then enters the room, has a quick look around, and announces:

"Every minute, on the minute, anyone who knows that on their back they have a blue label, must leave the room. Each person must decide whether or not to leave without knowing what other people are deciding to do at that moment. I can now tell you that there is at least one blue label on the back of someone in this room. No talking is allowed. Your first announcement is...now."

If there are in fact n blue labels, how long will it be before anyone leaves the room? How many people will leave the room in total at that time?

The solution

There is an unstated assumption in this puzzle: that everyone in the room is good at logic! And perhaps another unstated assumption is that the person who makes the announcement is telling the truth!

With these two assumptions, imagine what would happen if there was only one person in the room who had a blue label. In this situation, that person would know immediately that their own label was blue - because they can see everyone else's back and can't see any blue label. So that person immediately leaves the room.

Now everyone else knows that that person has to have been the only person who had a blue label - otherwise they would not have left, because they would have seen another blue label and would have stayed. So in particular, everyone else knows that they themselves must have a yellow label; and noone else needs to leave the room at any time.

So in this situation (n=1), 1 person leaves at t=0, and noone else leaves at any time.

Now suppose there are two people who have blue labels. Each of these people has looked around and knows that there is another person with a blue label. So the announcement that at least one person has a blue label gives neither of those people any immediate information about the colour of the label on their own back. Neither moves. but then each realises that the other must be able to see a blue label - otherwise the other would have left immediately. Since neither can see any more than one blue label, each then deduces that their own label must be blue, and after 1 minute, leaves the room. Everyone else deduces that those must be the only two people with blue labels, otherwise they would not have acted so, and stays in the room.

So in this situation, 2 people leave the room at t=1 minute, and noone else leaves at any time.

In general, if n is the number of blue labels, then n people - all those with blue labels - leave the room after n-1 minutes, and everyone else stays in the room.


Back to main puzzle page

Comments

common knowledge

The unstated assumptions are not that everyone in the room is good at logic and that the person who makes the announcement is telling the truth, but that these two facts are common knowledge (see http://en.wikipedia.org/wiki/Common_knowledge_%28logic%29). The mere facts themselves don't lead to the solution, since all assumptions of the form "(everyone thinks that)*k everyone in the room is good at logic" for k from 0 to n-2 and "(everyone believes that)*k the person who makes the announcement is telling the truth" for k from 0 to n-1 are used at some point in the deduction.