How many strategies are there for this puzzle where one of n logicians must call his own hat's color among n?

Question

$n$ logicians are wearing hats which can be of $n$ different colors. 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 calls the color of his own hat.

Mathematically, a strategy is an element of $(C^{n-1} \to C)^n$ where $C$ is the set of hat colors ($\mathrm{card}(C) = n$); a strategy $(d_0,\ldots,d_{n-1})$ is given by the decision procedures of each logician, where logician $k$ calls out $d_k(h_0, \ldots, h_{k-1}, h_{k+1}, \ldots, h_{n-1})$ when the hat colors are $(h_0, \ldots, h_{n-1})$.

One winning strategy for this classic puzzle is

having numbered the logicians and the colors, each logician calls the color that is his own number minus the sum of the hat colors that he sees (all modulo $n$). Then whoever has the number corresponding to the sum of the colors is calling out his own hat's color.

This isn't the only solution. (Hint: the case $n=2$ is easy. Now concentrate on $n=4$ and try to reduce it to the previous case.)

You can rephrase the strategy above this way: let $h_0, \ldots, h_{n-1}$ be the hat colors of logicians $0, \ldots, n-1$; logician $k$ calls out the value of $h_k$ that makes the equation $h_0 + \ldots + h_{n-1} = k$ true. More generally, equip the set of colors $C = \{c_0, \ldots, c_{n-1}\}$ with any group structure $(C, *)$, and assign each logician a unique color $\ell_k$; then a winning strategy is for each logician $k$ to solve the equation $h_0 * h_1 * \ldots * h_{n-1} = \ell_k$ for $h_k$ and call out the solution. Hence every group structure leads to a winning strategy.

Are the strategies presented above are all there is? If not, is there a reasonable way to describe the collection of all winning strategies, such as relating them to another well-known mathematical structure? For example, how many distinct strategies are there for a given $n$?

Answer 1

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