Number the people \(1,\dots,n\) from the front to the back.
Number the hats from \(0\) to \(m-1\), so that formulas that use the modulo operator come out simpler.
Imagine the strategy written out as a table with \(n\) columns, where each row has one possible sequence of \(n-1\) hat numbers followed by the corresponding guess person \(n\) should make in that situation. Remember that the guess must always be distinct from the \(n-1\) numbers in the row, so we are choosing one of the \(m-(n-1)\) available numbers for each row.
Characterization 1: We claim that a strategy is successful if and only if it has the following property: if we cover any one of the first \(n-1\) columns, the rows must still be all distinct.
Proof: For the person corresponding to the column we covered, the values on the left are what they see and the values on the right are what they have heard. If each row is still unique, this means that for each combination of seen+heard information this person can determine the correct row of the original table and thus their hat number. And if there is a collision, this means that there are two possible situations in which this person receives the same information – and as the rows of the original table are distinct, we can be sure that in these two situations our person has two different hat numbers.
Characterization 2: Now let’s go back to looking at the strategy as a function \(f(h_1,\dots,h_{n-1})\). Suppose we fix \(n-2\) of its arguments and vary the last one left: the value \(h_i\). There are \(m-(n-2)\) options for the hat number \(h_i\), and exactly the same \(m-(n-2)\) options for the last person’s guess. And if two values \(h_i\) produced the same guess, it would obviously break the condition we described above and create two indistinguishable scenarios for person \(i\). Thus, each of these one-variable functions must be injective, and more precisely a permutation without any fixed points (as person \(n\)’s guess also cannot be \(h_i\)). And we can easily verify that this condition is not only necessary but also sufficient for a strategy to be successful.
In this section we will describe efficient constructions of successful strategies for some special cases. These loosely correspond to some of the given subtasks.
Case n = m
As illustrated in the example, each person’s guess is forced. They can’t lose.
Case n+1 = m
One hat remains unused. Imagine that it’s placed behind the last person in the row. From this person’s point of view, there are now two possible permutations of all \(m\) hats: one correct and one in which their hat and the hat behind them are swapped.
One successful strategy can be described as follows:
Case n = 4, m is a power of 2
Probably the funniest/cutest partial solution:
Suppose the three hats seen by the last person are \((a, b, c)\) and that \(m=2^k\).
Consider the value \(a \oplus b \oplus c\), where \(\oplus\) denotes the binary XOR. Observe that:
Case n = 3
Imagine the strategy written down into a 2D table of dimensions \(m\times m\), with value \(f(a,b)\) in row \(a\), column \(b\). Note that the main diagonal remained empty. And from characterization 2, we know that each row and each column contains a permutation of all values other than its own index.
This means that if we now fill in the main diagonal by setting \(f(a,a)=a\) for all \(a\), we will get a valid Latin square. And vice versa, any such Latin square represents a valid strategy for three people.
Latin squares of this type (with the main diagonal containing sequential values) are called idempotent and they do exist for all \(m\geq 3\).
For odd \(m\) there are some easy constructions. E.g., we can set \(f(a,b)=((a+b)(m+1)/2)\bmod m\). This is a Latin square because \(2\) is invertible modulo an odd \(m\) and it is idempotent because \(f(a,a)=(m+1)a\bmod m = a\).
Note that the above Latin square is symmetric: \(f(a,b)=f(b,a)\). Symmetric idempotent Latin squares only exist for odd \(m\). This is because in these Latin squares each value must have an odd number of occurrences (one on the diagonal + the rest comes in pairs). Hence, our construction for even \(m\) will have to be different.
It’s interesting to observe what this means in the context of the task: while for \(n=3\) and odd \(m\) the last player has a strategy when the answer only depends on the unordered pair \((a,b)\) of hats seen, for even \(m\) no such strategy exists – for every successful strategy the order of hats matters.
One possible efficient construction of an idempotent Latin square for an even \(m\):
Let \(q=m-1\) (hence \(q\geq 3\)) and let \(r=(q+1)/2\). We’ll start by constructing the \(q\times q\) Latin square \(M\) as described above, and then we’ll tweak it to get a square that’s one bigger.
Consider the main diagonal cyclically shifted by one: the cells \(T\) of the form \((x, (x+1) \bmod q)\). The entries in these cells are also all distinct: \(M(x, x+1) = (x+r)\bmod q\).
We will now add row and column \(q\) to \(M\) and rearrange stuff as follows:
Verification that this works is left as an exercise :)
Small test cases can be resolved by writing the constraints as some form of a constraint satisfaction program such as SAT. This approach can find solutions for cases like \((4, 6)\), \((5, 7)\), \((6, 8)\), and also prove the unsolvability of cases \((4, 7)\) and \((7, 9)\).
Note that this is our first encounter with unsolvability: there are indeed some combinations of \(n\) and \(m\) for which no successful strategy exists.
Also note that there is no monotonicity in either variable. This can be quite unintuitive to many people. E.g., we already know that for \(n=4\) people we have solutions for \(m=4,5,6\) hats. After discovering that \((4, 7)\) is unsolvable, many would expect that \((4, m)\) will now be unsolvable for \(m > 7\) as well. However, we already know that \((4, 8)\) is solvable again. What’s up with that?!
Another way of thinking about the problem is trying to find some other forms of monotonicity – i.e., other construction of bigger solutions from smaller ones or vice versa.
Claim: If \((n,m)\) has a successful strategy, so does \((n-1,m-1)\).
Constructive proof: Let \(f\) be any successful strategy for \((n,m)\). For any \(t = (h_1,\dots,h_{n-2})\) such that none of them is the largest hat number \(m-1\), let’s define \(g(t)\) as follows: \(g(t)\) will be the (always existing and unique) value \(x\) such that \(f(t,x) = m-1\). Then \(g\) is a successful strategy for \((n-1, m-1)\).
To see why this construction works, recall that from Characterization 2 we know that \(x \not= m-1\), so all values returned by \(g\) are valid hat numbers, and as \(x \not\in t\), \(g(t)\) is a valid guess. Additionally, \(g\) satisfies Characterization 1 because having \(g(t) = g(t') = x\) for \(t, t'\) that only differ in one coordinate would mean that \(f(t,x) = f(t',x) = m-1\) and that would contradict \(f\) being a successful strategy in the original case.
The above result can actually be read as a form of monotonicity.
Indeed, let’s fix the difference \(d = m-n\) between the number of hats and people, and let’s look at the corresponding diagonal, i.e., all settings of the form \((n, n+d)\). The above result tells us that as we go along the diagonal, an unsolvable instance cannot be followed by a solvable one. Thus, either the entire diagonal is solvable or there is exactly one place where we transition from solvable instances into unsolvable ones.
Any Steiner system \(S(n-1, n, m)\) with block size \(n\) gives us a fully order-independent strategy for these specific values \(n\) and \(m\), as follows: for the set \(T = \{h_1,\dots,h_{n-1}\}\) (regardless of the order in which these \(n-1\) hats are seen) announce the unique element \(d \in B \setminus T\) where \(B\) is the unique block containing \(T\).
Hanani’s theorem tells us that for \(n=4\) these Steiner systems, i.e., \(S(3, 4, m)\), exist if and only if \(m\in\{2,4\} \pmod 6\). We also know that there is a unique (up to isomorphism) Steiner system \(S(5,6,12)\) that solves \((6, 12)\) and by the above construction also \((5, 11)\).
The results listed above are sufficient to solve all the given subproblems. (See the implementation of the solution of D8 for details on how those instances are constructed.) How far beyond that can we go? Is it possible to do a complete characterization of solvable instances? If the answer interests you, have fun exploring :)
