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

$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$?

• Would you please give all the information on 2 and 4 that you have? This is a question, not a challenge to make us work, right? – Phira Nov 6 '11 at 0:10
• Yup. This is fun! Though (as a kinda coding theorist) I like that version even better, where there are only two colors. The logicians have the option to call a color or pass... and the rule is that if any single one calls a wrong color, they all lose as a team. The object is then to device a strategy that maximizes the chance of the team winning (to the best of my knowledge they cannot guarantee a win). – Jyrki Lahtonen Nov 6 '11 at 8:18
• You have to take an Abelian group for this to work. – Phira Nov 6 '11 at 8:19
• @Phira: Well, since you deleted the comments there's no way of telling now whether you'd pointed to anything concrete. I suggest you do so now. So far, I can see neither an inconsistency in definitions of the $c_i$, nor an error in the product strategy. – joriki Nov 6 '11 at 9:35
• @Phira: The $c_i$ are the colours of the actual hats. The players don't multiply the colours of other people's hats; they solve the equation $c_1\ldots c_{n-1}=l_k$ for $c_k$, as described in the second box. The result is $c_{k-1}^{-1}\ldots c_1^{-1}l_kc_{n-1}^{-1}\ldots c_{k+1}^{-1}$. As I pointed out in a comment above, they could use any other order for the product, as long as they all use the same. – joriki Nov 6 '11 at 10:29

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];

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

• Why can you choose a different bijection between the group elements and the colors for each player? – Phira Nov 7 '11 at 12:41
• @Phira: There's no connection between these bijections. All we need is a function that assigns to each combination of hat colours some number from $0$ to $n-1$ such that the number and any $n-1$ of the colours uniquely determine the $n$-th colour. There's nothing in this which requires us to choose the same bijection for each player; we just need them to be bijections individually so that we can map back and forth between colours and group elements. – joriki Nov 7 '11 at 13:30