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