7
$\begingroup$

Hat guessing Game is played by a team of one-hundred players with hats that can be any of 100 different colors. (Not all colors need to be used.) Each player can see only the colors of 99 hats worn by the rest of the team; no player can see the color of his or her own hat. The players are to guess the colors of their own hats, and if at least one player guesses correctly then the team as a whole wins. The players may not communicate in any way during the game, and they must all announce their guesses simultaneously. Find a strategy which will guarantee them success for every possible arrangement of hats.

Answer from "A dozen hat problems" :

Label the hat colors 0 to 99 and number the players 0 to 99. Have each player sum the colors she sees, working mod 100, and guess the color number that brings this sum up to the number she has been assigned as a player, again working on mod 100.

I try n=3 using this strategy and found that one player will make a correct guess. But I still cannot figure out how this strategy comes. Please suggest.


Thank you, Wildcard.

Let $a_i$ be the hat color number of player numbered $i$, where $i\in\{0, 1, \ldots, 99\}$

(If player numbered $1$ wear the same color hat as player numbered $8$ , then $a_1 =a_8$)

$a_0+a_1+\ldots+a_{99} \equiv k (\bmod{100})$, where $k\in\{0, 1, \ldots, 99\}$

so $a_k \equiv k-a_0-a_1-\ldots-a_{99}+a_k(\bmod{100})$

Therefore, the player whose hat color number is $a_k$ and is the player numbered $k$, is the only one who makes the correct guess. The rest will guess wrong.

$\endgroup$
  • $\begingroup$ Do you mean that you didn't understand the strategy or you didn't understand how this strategy is found? $\endgroup$ – Merdanov Aug 25 '17 at 3:24
  • 1
    $\begingroup$ It sounds to me (and is what I would be interested in hearing too) like he is asking for a proof of why the strategy works. $\endgroup$ – JMoravitz Aug 25 '17 at 3:25
  • $\begingroup$ @Merdanov, I mean how this strategy is found. $\endgroup$ – carat Aug 25 '17 at 3:26
  • $\begingroup$ Regarding checking your understanding: your symbolic proof is good, but only proves that player $k$ guesses right. It doesn't demonstrate that no one else does (though this is true). I'll see about adding a full symbolic proof to my answer later on. $\endgroup$ – Wildcard Aug 31 '17 at 21:00
  • $\begingroup$ @Wildcard.From $a_k \equiv k-a_0-a_1-\ldots-a_{99}+a_k(\bmod{100})$, though $a_k$ may be the hat color number of more than one player but only one player is numbered "$k$", so I think, no one else, beside player numbered $k$, will guess right. $\endgroup$ – carat Sep 1 '17 at 14:19
6
$\begingroup$

The key to this is that the ACTUAL sum of all the hats (mod 100) must be one of the numbers from 0 to 99.

Whichever number it is, that player will have guessed his/her hat color correctly.

A corollary: no one else will have guessed correctly. Only the person whose player number matches the actual sum of the hat colors (mod 100) will have guessed right.


Worked out example

Edit to answer this comment:

Your answer is clear in case that the hat color of each player are all different and in case that the hat color of all the players is just one color, say 100 green. But I'm not clear in case there are some repetition of colors, say 40 red, 30 green, 20 blue and 10 yellow. I think there will be 4 groups of 40, 30, 20, 10 different answers. What will guarantee the success ? Will there be more than one correct guess ? Please explain in more details on this point.

Let's work out your example. First, let's assume the colors are numbered like so:

  • 13 - red
  • 36 - green
  • 45 - blue
  • 79 - yellow

(Remember, there are another 96 colors available that DON'T happen to be used, but could be.)

And let's say that the players are as follows:

  • players 0, 10, 20, 30, 40, 50, 60, 70, 80, 90 are wearing yellow hats
  • players 7, 17, 27, 37, 47, 57, 67, 77, 87, 97, 71, 72, 73, 74, 75, 76, 78, 79, 2, 3 are wearing blue hats
  • the thirty players in the range 1-40 who have not already been named are wearing green hats
  • every other player is wearing a red hat.

Exactly one player will guess right. Who will it be?

To work that out, compute the sum of all the hat colors, mod 100:

$$(13\times40)+(36\times30)+(45\times20)+(79\times10) \mod 100$$ $$20+80+0+90\mod 100$$ $$90$$

Player 90 will guess his hat color right.

How will he do that? Well, player 90 (who is wearing a yellow hat) will see the following hats:

  • 9 yellow hats - $79\times9\equiv11\mod100$
  • 20 blue hats - $45\times20\equiv0\mod100$
  • 30 green hats - $36\times30\equiv80\mod100$
  • 40 red hats - $13\times40\equiv20\mod100$

He will then total these to 11 (mod 100), and to make the total sum congruent to his own player number of 90, he will guess color 79 (which is yellow).

(Edit to add: regardless of which players are wearing which hats, if there are 40 red, 30 green, 20 blue and 10 yellow and the colors are numbered as above, player 90 will be the one to guess right no matter what color hat he is wearing. Because he will compute his guess, taking into account all 99 hats he sees, such that the sum of those hats plus the hat color he is guessing is congruent to his player number, mod 100.)

Note that player 56 will ALSO guess color 79 (yellow), but player 56 is wearing a RED hat.

Player 56 will compute the sum of all hats he can see like so:

$$(13\times39)+(36\times30)+(45\times20)+(79\times10) \mod 100$$ $$7+80+0+90\mod 100$$ $$77$$

To make the total sum congruent (mod 100) to his player number of 56, he will guess color 79. (Because $79+77=156\equiv56\mod100$)

By contrast, player 30 (who wears a yellow hat) will compute:

$$(13\times40)+(36\times30)+(45\times20)+(79\times9) \mod 100$$ $$20+80+0+11\mod 100$$ $$11$$

Note this is the same partial sum that player 90 reached. However, player 30 will not guess the color 79 (because 79+11 = 90 and he is not player 90). Instead, he will guess color 19, whatever that is. Maybe it's purple. Since he doesn't have a purple hat, his guess is wrong.

So it's NOT guaranteed that each color is guessed once. It's NOT guaranteed that each guess is different. (These statements are equivalent. And they can happen, for instance in the case where everyone wears a green hat.)

What is guaranteed, is that exactly and only one guess will be correct, and the rest will be wrong.


Symbolic Proof

Let $a_i$ be the hat color number of player numbered $i$, where $i\in\{0, 1, \ldots, 99\}$

(Example: if player number $1$ wore the same color hat as player number $8$, we would write $a_1 =a_8$.)

Thus, any player $k$ knows the value of $k$, but not the value of $a_k$. (This is given in the puzzle and requires no proof.)

Let $S$ be the sum of all hat colors mod $100$; to be precise:

$$(S \in \{0,1,\ldots,99\}) \land (S \equiv \sum_{i=0}^{99} a_i \mod 100)$$

No player knows $S$. However, any player $k$ may compute the value $P_k$ (for "partial sum as known to player $k$") which we may compute as follows:

$$P_k \equiv S-a_k\mod100$$

The player computes this as follows:

$$P_k \equiv \sum_{0\le i\le99, i\ne k}a_k \mod100$$

In other words, by adding all hat colors visible to that player (and reducing it mod 100).

Each player $k$ assumes that the actual sum $S$ is equal to that player's player number: i.e. it's assumed by any player $k$ that $S=k$.

Thus player $k$ shall make guess $G_k$ (for the value of $a_k$) such that:

$$G_k \equiv k-P_k \mod 100$$

We can see (by adding $P_k$ to both sides) that $G_k + P_k \equiv k \mod 100$. In other words, the guessed color plus the sum of all visible hat colors, mod 100, equals the player's number.

But $S \equiv P_k + a_k$, so that $G_k = a_k$ (i.e. the guess is correct), if and only if $S\equiv k \mod100$.

By the pigeonhole principle, there is only one $k$ such that $S \equiv k \mod 100$.

Therefore, the only player who shall guess correctly is player number $S$, and the rest shall guess wrong.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. Your answer is clear in case that the hat color of each player are all different and in case that the hat color of all the players is just one color, say 100 green. But I'm not clear in case there are some repetition of colors, say 40 red, 30 green, 20 blue and 10 yellow. I think there will be 4 groups of 40, 30, 20, 10 different answers. What will guarantee the success ? Will there be more than one correct guess ? Please explain in more details on this point. $\endgroup$ – carat Aug 25 '17 at 4:24
  • $\begingroup$ @carat, I grant this is a highly unintuitive result without a diagram. I will add one later. :) $\endgroup$ – Wildcard Aug 25 '17 at 4:26
  • $\begingroup$ @carat, I just read your comment more carefully. The thing you are forgetting is that the players have numbers, too. So two players who both have blue hats are still distinguishable, because they have different player numbers. They will both see the same arrangements of hats on the heads of the other 99 players, BUT they will make different guesses, according to their player numbers. $\endgroup$ – Wildcard Aug 30 '17 at 21:02
  • 1
    $\begingroup$ @carat, I've added a fully worked out example. $\endgroup$ – Wildcard Aug 30 '17 at 21:27
  • $\begingroup$ Please check my understanding above. $\endgroup$ – carat Aug 31 '17 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.