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
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!
No comments:
Post a Comment