# 1000.57 – A Line of Men

Imagine that you are in a large sunlit room, standing by the head of a line of men who are standing one behind the next, each of whom has a spot on his forehead, either red or blue. The colors are randomly distributed in the line. No one can see his own spot, of course, nor the spots of any of the men ahead of him. Further, no one may turn to see the spot of any man behind him. And finally, the men may not communicate with each other in any way. Thus no man knows the color of any man's spot, including his own.

These men are tasked with going up ahead, one by one, to form a row of men standing side by side, shoulder to shoulder facing you, with all the blue spotted men together on one side and all the red spotted men on the other! That is, when all the men have passed you and have gone up and joined the row, you, standing where you are, will see them all, with their colored spots neatly sorted out, blues on one side and reds on the other.

How is this to happen? Ah, it's because you are giving the same simple instruction to each man as he reaches the head of the line and is ready to walk up to join the row that is forming, telling him how to do it. (You've told the first man to walk up and stand wherever he likes.)

Each man (after the first) gets the same instruction from you, which he can carry out without knowing the color of his own spot. He can see ahead to the growing line of men standing side by side, so he can see the emerging row of sorted-out colors, and of course he can use what he sees to decide where to join the row, even though he doesn't know the color of his own spot. What will your instruction be?

Solution

Here is what you tell each man. "As you approach the row, if all the colored spots are the same, you can join the row at either end. If, however, there are blues on one side and reds on the other, go up and join the row at the interior point where the color changes."