Combinatorics – Hat Guessing Game Explained

combinatorics

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.

Best Answer

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.

Related Solutions

[Math] How many strategies are there for this puzzle where one of n logicians must call his own hat’s color among n

Here's a partial answer: No, these are not the only strategies. For $n=3$, there are $10752$ different strategies, only $24$ of which arise in the manner you describe. (Let's call them "product strategies".)

First, to count the product strategies, we can make use of the fact that there is only one group with three elements and it is abelian. Thus the order in the product is irrelevant, and the only things to choose are the $l_k$ and the three bijections between the colours and the group elements for each logician. That makes four choices with $3!$ possibilities each, but many of these lead to the same strategies. To see this, note that the permutations of the remainders modulo $3$ can all be written as $r\to\sigma r+t$ with $\sigma=\pm1$. The additive constants $t$ of all four options can be assembled into a single one, so we only have one additive constant (three possible values) and four signs. However, we can multiply the entire equation by $-1$, which leaves only three independent signs, with two possible values each, for a total number $3\cdot2^3=24$ of possibilities. This is confirmed by a computer search.

Below I give a listing of a program that finds all strategies for $n=3$. It finds $10752=2^9\cdot3\cdot7$ of them. Here's one that isn't a product strategy:

$$ \begin{array}{c|ccccccccc} &00&01&02&10&11&12&20&21&22\\\hline d_0&0&0&1&0&1&2&1&2&2\\ d_1&2&1&2&0&2&1&0&1&0\\ d_2&2&2&1&1&0&2&1&0&0\\ \end{array} $$

You can check that it's a strategy by going through the $3^3$ cases, and you can see it's not a product strategy because a product strategy couldn't have $d_0(0,0)=d_0(0,1)=0$.

Some interesting facts that may point towards a solution: For $n=3$, there is no individual choice left in any of the strategies; that is, for any two individual strategies $d_0$ and $d_1$ there is never more than one strategy $d_2$ to complete them. Also, for $n=3$ in each strategy each player guesses each colour for the same number of combinations. And generally (not just for $n=3$) only one player guesses correctly for each combination; this follows because the expectation value of a correct guess is $1/n$, so if there were combinations with more than one correct guess there would have to be one with no correct guess. All this may point to some magic-square-like description of the solutions.

Here's the code:

import java.util.Set;
import java.util.HashSet;

public class Hats {
    final static int n = 3;
    final static int UNKNOWN = -1;
    static int [] [] [] strategy = new int [n] [n] [n]; // [player] [first hat seen] [second hat seen]

    static int [] [] permutations = {
        {0,1,2},
        {0,2,1},
        {1,2,0},
        {1,0,2},
        {2,0,1},
        {2,1,0}
    };

    static int [] [] inversePermutations = new int [6] [3];

    static {
        for (int i = 0;i < 6;i++)
            for (int j = 0;j < 3;j++)
                inversePermutations [i] [permutations [i] [j]] = j;
    }

    static Set<Integer> productStrategies = new HashSet<Integer> ();

    public static void main (String [] args) {
        // generate all product strategies
        int [] p = new int [3];
        for (p [0] = 0;p [0] < 6;p [0]++)
            for (p [1] = 0;p [1] < 6;p [1]++)
                for (p [2] = 0;p [2] < 6;p [2]++)
                    for (int g = 0;g < 6;g++) {
                        for (int player = 0;player < 2;player++)
                            for (int first = 0;first < 3;first++)
                                for (int second = 0;second < 3;second++)
                                    strategy [player] [first] [second] =
                                        inversePermutations [p [player]]
                                        [(permutations [g] [player] -
                                          permutations [p [(player + 1) % 3]] [first] -
                                          permutations [p [(player + 2) % 3]] [second] + 9) % 3];

                        productStrategies.add (getCode ());
                        if (!isCorrect ())
                            throw new Error ();
                    }

        System.out.println ("Found " + productStrategies.size () + " different product strategies");

        // generate all strategies
        recurse (0);

        System.out.println ("Found " + count + " different strategies in all");
    }

    final static int [] colours = new int [n];
    static int count;
    static int total;

    // returns a unique integer code for the strategies of the first two players
    static int getCode () {
        int result = 0;
        for (int player = 0;player < 2;player++)
            for (int first = 0;first < 3;first++)
                for (int second = 0;second < 3;second++)
                    result = 3 * result + strategy [player] [first] [second];
        return result;
    }

    // checks whether the strategies of the first two players allow for a strategy of the third player
    // returns true if there is one strategy, false for none, throws an error if there is more than one
    static boolean isCorrect () {
        for (int i = 0;i < n;i++)
            for (int j = 0;j < n;j++)
                strategy [2] [i] [j] = UNKNOWN;

        // for each combination of hat colours, check whether one of the first two players guesses correctly;
        // if not, this fixes a value in the third player's strategy
        for (colours [0] = 0;colours [0] < n;colours [0]++)
            for (colours [1] = 0;colours [1] < n;colours [1]++)
                for (colours [2] = 0;colours [2] < n;colours [2]++) {
                    if (strategy [0] [colours [1]] [colours [2]] != colours [0] &&
                        strategy [1] [colours [2]] [colours [0]] != colours [1]) {
                        // neither of the first two players guesses this combination correctly
                        int s = strategy [2] [colours [0]] [colours [1]];
                        int s0 = colours [2];
                        if (s == UNKNOWN)
                            // fix the third player's strategy in this case
                            strategy [2] [colours [0]] [colours [1]] = s0;
                        else if (s != s0)
                            // or conclude that there is no strategy if it was already otherwise determined
                            return false;
                    }
                }

        // check that there's only one strategy left for the third player
        for (int i = 0;i < n;i++)
            for (int j = 0;j < n;j++)
                if (strategy [2] [i] [j] == UNKNOWN)
                    throw new Error ();

        return true;
    }

    static boolean first = true;

    // generate all 3^18 combinations of strategies for the first two players
    static void recurse (int depth) {
        if (depth == (n - 1) * n * n) {
            if (isCorrect ()) {
                // this combination allows for a successful strategy of the third player -- count it...
                count++;
                if (first && !productStrategies.contains (getCode ())) {
                    // and if it's the first non-product strategy, print it as a TeX array
                    System.out.println ("non-product strategy:");
                    for (int player = 0;player < 3;player++) {
                        for (int first = 0;first < 3;first++)
                            for (int second = 0;second < 3;second++)
                                // internally first and second are cyclic; for output the order is reversed for the second player
                                System.out.print ("&" + strategy [player] [player == 1 ? second : first] [player == 1 ? first : second]);
                        System.out.println ("\\\\");
                    }
                    first = false;
                }
            }
        }
        else {
            int player = depth / (n * n);
            int first = (depth / n) % n;
            int second = depth % n;
            for (int guess = 0;guess < n;guess++) {
                strategy [player] [first] [second] = guess;
                recurse (depth + 1);
            }
        }
    }
}

[Math] A riddle with a witch and some gnomes (guessing numbers on hats)

The sum of the numbers on all of the hats must be congruent to one of $0, 1, 2 \pmod{3}$. If a gnome knows the sum of all the hats $\pmod{3}$ and the sum of the other gnomes' hats $\pmod{3}$, he can subtract to get the number on his hat $\pmod{3}$, and thus, the number on his hat.

Since the gnomes don't know the sum of all the hats $\pmod{3}$, they do the following: gnome $1$ assumes that the sum of the numbers on all the hats is $1 \pmod{3}$, gnome $2$ assumes that the sum of the numbers on all the hats is $2 \pmod{3}$, and gnome $3$ assumes that the sum of the numbers on all the hats is $0 \pmod{3}$. They each calculate the number on their hat based on this assumption. One of these gnomes must have made the right assumption, and thus, guesses their hat correctly.

For $n$ gnomes, the $i$-th gnome assumes the sum of the numbers on all of the hats is $i \pmod{n}$, and guesses his hat accordingly. By the same logic, one of the gnomes guesses correctly.

Note: No matter what the $n$ gnomes' strategy is, the probability of any gnome guessing correctly is still $1/n$. This means that the expected number of gnomes to guess correctly is always $n \cdot 1/n = 1$. Thus, if the gnomes' strategy has a non-zero probability of having two or more gnomes guess correctly, there will also be a non-zero probability of having zero gnomes guess correctly. Therefore, in any strategy that guarantees that at least one gnome guesses correctly, exactly one gnome guesses correctly every time (no more and no less).