Logicians

Question:

At the Secret Convention of Logicians, the Master Logician placed a band on each attendee’s head, such that everyone else could see it but the person themselves could not. There were many different colours of band. The Logicians all sat in a circle, and the Master instructed them that a bell was to be rung in the forest at regular intervals: at the moment when a Logician knew the colour on his own forehead, he was to leave at the next bell. They were instructed not to speak, nor to use a mirror or camera or otherwise avoid using logic to determine their band colour. In case any impostors had infiltrated the convention, anyone failing to leave on time would be gruffly removed at the correct time. Similarly, anyone trying to leave early would be gruffly held in place and removed at the correct time. The Master reassured the group by stating that the puzzle would not be impossible for any True Logician present. How did they do it?

.

.

C

A

P

T

A

I

N

I

N

T

E

R

V

I

E

W

.

.

Solution: This is general induction plus a leap of logic.

Leap of logic: Every color must appear at least twice around the circle. This is because the Master stated that it would not be impossible for any Logician to solve the puzzle. If any color existed only once around the circle, the Logician who bore it would have no way of knowing that the color even existed in the problem, and it would be impossible for them to answer.

Each of the Logicians can look around the circle and count the number of times they see each color. Suppose that you are one of the Logicians and you see another color only once. Since you know each color must exist at least twice around the circle, the only explanation for a singleton color is that it is the color of your own band. For the same reason, there can only be one such singleton color, and so you would leave on the first bell.

Likewise, any Logicians who see another color only once should be able to determine their own color, and will either leave with dignity or be thrown out as an infiltrator. Equivalently, any color for which there are only two bands of that color will be eliminated after the first bell has rung. Thereafter there must be at least three bands of any remaining color.

Suppose you do not see any color once, but you do see a color twice. If these were the only bands of this color, then these two Logicians ought to have left at the first bell. Since they did not, that can only be because your own band is the same color so you can leave at the second bell.

Therefore, every logician would watch until a group of a given color that they expected to leave failed to leave. Then they would know that they had that color, and would leave on the next bell.

When only one color remained, that color would all leave on the next bell, because they would know that they could not have any other color (since then it would be impossible for them to know their color).