N logicians wearing hats of N colors

Question

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.)}

Answer 1

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!

Answer 2

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.

Answer 3

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 %:

3. 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.
4. 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.

Answer 4

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

• Assign a number to each colour
• Assign a leader
• 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.

Answer 5

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..