N logicians wearing hats of N colors

N logicians are wearing hats which can be of N different colors (each hat has one color; there can be multiple hats with the same color). Each logician can see the colors of all hats except his own. The logicians must simultaneously call out a color; they win if at least one logician calls the color of his own hat. They can agree on a strategy beforehand; the set of possible colors is known. There is a winning strategy (i.e. the logicians can arrange to win no matter what colors the hats end up being).

(I definitely didn't invent this; I don't know who did.)

I know of a solution that requires a little knowledge of abstract algebra (you can read a sketch of that solution on Math Stack Exchange). Is there a solution that doesn't require any mathematical background?

Specifically, how do you explain the solution to someone who isn't familiar with modulo arithmetic ($\mathbb{Z}/n\mathbb{Z}$)?

(Hint, if you want to try to solve it on your own: start with N=2 — white hat and black hat. Then work on N=4 — red, pink, blue and cyan.)

• Well, as a preliminary solution, it seems as if every logician just calls out randomly, they have about a 63.2% chance of winning anyway. You're looking for one that works 100%, though, right? – Joe Z. May 15 '14 at 23:53
• @JoeZ. I'm not interested in probabilistic solutions, only in a guaranteed solution (which exists). If the logicians lose, they'll be killed. And none of them are suicidal. – Gilles May 15 '14 at 23:59
• I just wanted to make sure it's not one of those where if one of them gets it wrong, they also all get killed, and some of them have to choose not to say anything. – Joe Z. May 16 '14 at 0:01
• It doesn't matter if one of them gets it wrong: they win as long as at least one color is called correctly. – Gilles May 16 '14 at 0:02
• Anyway, for N=2, the solution seems to be that one person will always say the same colour as the one he sees, and one will always say the opposite colour. – Joe Z. May 16 '14 at 0:03

There are two secrets to this question. First is to realise that you want no player in the circle to guess that the circle looks the same. If they guess the same circle, it is a wasted guess.

For these examples, the distinct colors are B (black), W (white), G (grey), N (neon), and F (fish). There are $N$ players and $N$ color hats.

If there is never a chance you could both be correct in this one specific puzzle, there is never a chance you could both be wrong. This has to do with the fact that there are $N \, N$ possible patterns of colors and each player can eliminate $N \, (N-1)$ possibilities by looking at the others. The remaining $\frac{N \, N}{N\,(N-1)}=N$ possibilities must all be guessed somehow.

$N=2$

For two players this is easy. One of you simply says: you guess we have the same color while I guess that we have a different. If the colors are BB or WW, the first person will guess correctly. If they are BW or WB the second person will. If they were to decide "I pick B you pick W or we both pick B" then there is a chance they could both be correct and an equal chance you could both be wrong.

$N=3$

If we have three players, each player needs a slightly different strategy to make this work! Decide, therefore, to elect an equalist (player 1) who believes that either every seat is the same (all the same color) OR every color is the same (all colors appear once). If he sees BB he guesses B. If he sees BW he guesses G.

The person in the chair to his right (player 2) knows what player 3 is wearing and what player 1 is wearing as well as player 1's strategy. If player 3 is B and player 2 thinks he is B, player 1 will guess B. There is no point in player 2 guessing that he is the same as the other two if they are equal, therefore, so he guesses (for this case) W. If, however, the arrangement is B_G, picking W will backfire as player 1 will guess G.

The easiest way to do this is to say that the colors W, G, and B are in a circle holding hands like the children you must be. Player two figures out what color Player 1 would pick in his situation and picks the one to that color's right. Player 3 does the same but picks the color to the left.

$N \gt 3$

The strategies for all players for any number of players and colors must meet only two criteria: (a) every player (A) must be able to tell by looking at each other players what color A's hat must be in order for that other character to guess correctly; (b) all player's guesses must be coordinated by (a) so that they are all different. The previous examples show examples as to how this works. Essentially, there are only $N$ different colored hats you could be wearing and if the other players take care of $N$-1 of them, you only have 1 left to cover...

One strategy to do this is to give every player a "favorite" color and then each color a proper fraction. This fraction is the seat (starting at 0) that has it as their favorite divided by $N$. Aka if $N=5$: $\mathrm{B}=0$; $\mathrm{W}=\frac{1}{5}$; $\mathrm{G}=\frac{2}{5}$; $\mathrm{N}=\frac{3}{5}$; $\mathrm{F}=\frac{4}{5}$ You imagine that there is a circle in the center of the seats where every color is arranged in the same order as the favorite colors. For every colored hat you see, you rotate that circle by whatever fraction of a circle that color is represented by. When you are done, the color in front of each player is the color they would guess if they saw exactly what you see. You should guess the color in front of you! As these are all different and your answer is dependent on every other players' hat color, this strategy works.

There are likely other strategies that work for every $N\gt2$ but there do not seem to be any that are easier to visualize or generalize for any $N$ than this!

This answer attempts to give a dumbed down version of the answer on Math.SE.

Say there are two logicians, A and B; and two colors, $0$ and $1$.

Mr. A looks at his friend and guesses that they are wearing the same hat. Mr. B knows that Mr. A is predictable and will guess that they are the same, so he will guess they are different. Without knowing what either person saw we can see that all answers are covered.

Them being the same is the same as saying that the sum of their colors is equal to $0 \bmod 2$ as $0+0=0$ and $1+1=2=0 \bmod 2$. Them being different is, similarly, $1 \bmod 2$.

The easiest solution, therefore, is for every person to guess that the sum of all the colors' numbers is equal to their seat number $S$ modulo the number of people.

The way to see this is to note that the equation for 5 logicians and 5 colors is: $a+b+c+d+e=S \bmod 5$ where each variable refers to the color number of the player with the same name.

For Mr. A, he knows what $b$, $c$, $d$, and $e$ add up to be and only doesn't know $a$ so he guesses $S=0 \bmod 5$ which means that $a=0-b-c-d-e \mod 5$.

Mr. B, he knows what Mr. A will guess, so he guesses $S=1 \bmod 5$, so $b=1-a-c-d-e \mod 5$.

By the time we get through 5 guessers we will guess:

Mr. A: $S=0 \bmod 5$
Mr. B: $S=1 \bmod 5$
Mr. C: $S=2 \bmod 5$
Mr. D: $S=3 \bmod 5$
Mr. E: $S=4 \bmod 5$
which is of course every possibility.

As you make up colors (one person in a circle with only black and white hats can yell 'purple'), this means any number of players can guess at least one of their hats correctly for any number of colors less than or equal to the number of players.

• Is the mod operator too advanced for a non-mathematical answer? – kaine May 22 '14 at 19:08
• I think this use of mod is reasonably easy to explain. – Ross Millikan May 24 '14 at 21:30

The solution is very simple. The solution is very simple ones you know it. But may be you would like to give it a try first? (Though my answer looks relatively complicated, this is because I was required to explain operation % with very basic operations)

The Solution:

1. The logicians numerate themselves (L1, L2, ..., LN) and colours (C1, C2, ..., CN).
2. Let's introduce a new operation %, it's meaning please see below*. There are N equations:

1) (C1 + C2 + ... + CN) % N = 0
2) (C1 + C2 + ... + CN) % N = 1
...
N) (C1 + C2 + ... + CN) % N = N-1


Logician Li should suppose that equation number i is true. Then he extracts Ci from equation number i: Ci = (i - C1 - C2 - ... - C_(i-1) - C_(i+1) ... - CN) % N. He can do it because he knows all colours except Ci.

Obviously exactly one equation is true. Therefore correspondent logician will be correct.

*Definition of operation %:

1. Z = X % Y operation is defined in the following way: One needs to find R and K integer number, which satisfy: X = R + Y*K and 0 <= R < Y. Then Z = R.
2. This means that C1 + C2 + ... + Ci + ... + CN) % N = i is equivalent to C1 + C2 + ... + Ci + ... + CN = i + N*k, where k is integer. Ci is found as Ci = i + N*k - C1 - C2 - ... - C_(i-1) - C_(i+1) ... - CN or, applying % operation to both parts, since Ci is integer less than N: Ci = (i - C1 - C2 - ... - C_(i-1) - C_(i+1) ... - CN) % N.
• Sure, assuming enough mathematical background — namely knowledge of modulo arithmetic. I'm asking for a solution (or maybe a way to explain that solution) without mathematical background. – Gilles May 24 '14 at 23:15
• @Gilles, you are kidding? What does it mean? mod is operation of the same complexity as + and /. Formulate exactly which operations are allowed. – klm123 May 25 '14 at 4:49
• @Gilles, I believe you can't solve this puzzle with out analog of mod operation. I explained mod operation via * and / operation, so the solution can understand the one who knows only them and decimal notation of numbers. – klm123 May 25 '14 at 5:04
• Addition and division are taught in primary school. Modulo arithmetic is typically taught only in undergraduate if you're studying math (maybe in high school in some countries). I asked if there was a solution that doesn't require having studied math. – Gilles May 25 '14 at 9:08
• @Gilles I may not be versed in the arcane art of proper mathematics, but it seems to me that the subset of true modulo arithmetic involved in this answer was completely identical to the "remainder" concept in primary school mathematics. Anyone who understands the concept of remainders should be able to understand this answer. – March Ho Jan 8 '15 at 12:47

Since the set of colours is known in advance, then:

• Assign a number to each colour
• The leader arranges everyone else in numerical order, then stands at the end of the line
• The leader is passed down the line until in the correct place

If every hat is of a different colour, then each logician knows their colour from their place in the line.

If not:

• If more than 2 hats are of the same colour, at least one logician will be standing between two people with the same colour hat, so knows that they too have that colour
• The logicians agree in advance that if they only see colours repeat in groups of two, they call out the colour ahead of them in line rather than their own. That way the second member of a colour should be correct.

Non-mathematical, but does assume a lot of collaboration is allowed.

• I don't understand what you mean by “The leader is passed down the line until in the correct place”. Note that the logicians are not allowed to communicate, that includes verbal communication but also gestural communication such as moving around. – Gilles Apr 21 '15 at 13:32
• These questions require that there is no communication after the hats are added until they say their hat color. That isn't stated very clearly in the question though. This behavior of rearranging counts as communication. +1 though due to a correct solution to a question (even though it violates intended rules) – kaine Apr 22 '15 at 17:01

Say there are

5 logicians 1, 2, 3, 4, 5

& 5 colors A, B, C, D, E

One of the logician, say A, is chosen the leader. Everyone will call out the leader's hat color. The leader will call out the color that is missing from the remaining N-1 hat colors he can see. Two cases are possible:

If there is no repeating color, then it's easy to see that the leader will call out his own hat's color and they'll win. If there is a repeating color, then further two cases are possible:

• If the leader's color is repeated, then the logician with the same color as leader will call out his own color and they'll win.
• If the leader's color is not repeated but someone else's color is, then idk...

Help me to build upon this? This was too long for a comment..

• This fails in the case of your second bullet. The strategy in the link takes care of that. It makes sure each logician claims the sum of the hat colors is different. A good thought. – Ross Millikan May 16 '14 at 2:37
• I can't see how this approach could work. You're handling most cases, but not all of them. Think of the person who hands out the hats as an evil mastermind — if there's even a single way to make the logician fails, that's what he'll choose. Your task is to arrange for a strategy that always works. – Gilles May 16 '14 at 16:38
• I know this isn't the correct answer. It's just a thought, an idea that isn't complete yet. probably was better suited as a comment but was too long... – kBisla May 16 '14 at 17:29