Guessing colored hats without repetition

Question

This entire question is inspired by Problem $12082$ of the Problems and Solutions section of the American Mathematical Monthly (see the May $2020$ issue for the solution to said problem). First, I recall a simpler, classic problem, slightly rephrased. Then I will state the variant, which is the actual question I want to ask.

Classic question: Suppose that $n$ people are in a line (so that each can only see the people in front of them) and each has a hat placed on their head. The hats can be any of $k$ different colors, with equal probability of any color occurring (possibly with repetition). Starting from the back of the line, each person tries to guess the color of the hat on their own head. Certainly, the person at the back of the line can do no better than a random guess. But (assuming everyone strategizes beforehand and works as a team) can the last person in line make their guess in such a way that everyone else in the line will be able to guess their hat color with 100% certainty?

Classic answer: Replace the hat colors by elements of $\mathbb Z/k\mathbb Z$. If the colors of the hats are $C_1,C_2,\dots,C_n$, where $C_n$ corresponds to the last person in line, then the last person guesses $S=C_1+C_2+\dots+C_{n-1}$. When we get to person $j$, they can see $C_1,\dots,C_{j-1}$ and they have heard the guesses $C_{j+1},\dots,C_{n-1},S$. Therefore, they can recover $$C_j=S-(C_1+\dots+C_{j-1}+C_{j+1}+\dots +C_{n-1}).$$ (This is an example of a $(n-1)$-ary quasigroup of order $k$. In fact, the strategies for the classic question are precisely the same thing as $(n-1)$-ary quasigroups of order $k$.)

Variant question: Suppose that we are in the same setup, but there is now only one hat of each color (if the game is to be possible, we must have $k\geq n$). The person at the back of the line should guess one of the $k-n+1$ colors that is not visible to them (since they know that they cannot be wearing any of the colors on the heads of the other people). Again, is it possible for the person in the back to make a guess (which now should be restricted to the $k-n+1$ colors not on another head) that allows everyone else in line to guess the color on their head with 100% certainty?

Partial answer: Let us phrase the strategy we are looking for in slightly more abstract terms. For any integer $m>0$, let $[m]=\{1,2,\dots,m\}$. Then the hats visible to the last person in line correspond to an injection $f:[n-1]\rightarrow [k]$. Let $\mathcal I$ be the set of all such injections. Then the desired strategy is a function $S:\mathcal I\rightarrow [k]$ such that:

• $S(f)\notin \text{Im}(f)$ for any $f\in \mathcal I$;
• if $f_1(i)\neq f_2(i)$ for exactly one $i\in [n-1]$, then $S(f_1)\neq S(f_2)$.

The first condition says that the color being guessed is not already on someone else's head. The second condition says that each subsequent person can recover the color of their hat with 100% certainty. The ultimate question is now just: "For which $k$ and $n$ does $S$ exist?"

For $n=2$, we can identify a function $f:[1]\rightarrow [k]$ with its image, in which case the desired strategy is any bijection $S:[k]\rightarrow [k]$ with no fixed points. For $k\geq 2$, these certainly exist.

For $n=k$, the only possible strategy is to set $S(f)$ to be the unique element of $[k]\setminus \text{Im}(f)$.

For $n=3$, a strategy $S:\mathcal I\rightarrow [k]$ almost looks like a binary operation $[k]^2\rightarrow [k]$, but with the caveat that it is not defined on the diagonal of $[k]^2$. However, by defining $X^2=X$ for all $X\in [k]$, this extends to a binary operation, which is actually an idempotent quasigroup. Conversely, any idempotent quasigroup restricts to a valid strategy by ignoring the diagonal of $[k]^2$. This is the idea of the printed answer for the aforementioned Problem 12082 in the AMM, which then proceeds to construct idempotent Latin squares (which are the same thing as quasigroups) for $k\geq 3$. The same construction can be found in this paper on quasigroups by Bruck.

For $n>3$, I really have no idea what to do with this problem. Purely by virtue of free association, the prescribed conditions make me think of error-correcting codes (which are related to the classic question, as detailed in this MAA Focus article) and exterior algebras. But in terms of actual problem-solving, I am fairly stumped. I would be interested to see any thoughts that people have on cases with $n>3$, even if they only cover a few cases. It would also be interesting to come up with strategies for small values of $k-n>0$.

Answer 1

This is a very partial answer. A sufficient condition for the existence of such a strategy is the existence of an $S(n-1,n,k)$ Steiner system, known as a Steiner $n$-tuple system. Recall that for positive integers $1<t<n<k$, an $S(t,n,k)$ Steiner system is a collection $\mathcal C$ of $n$-element subsets of $\{1,\dots,k\}$, called blocks, such that every $t$-element subset of $\{1,\dots,k\}$ is contained in exactly one block.

Given a Steiner $n$-tuple system of order $k$, the corresponding strategy is simple; the person in back announces the unique color which, when added to the the set of $n-1$ colors they see, forms a block of the Steiner system. Each successive person does the same thing, using previously announced colors to supplement the color they see.

Unfortunately, very little is known about the existence of Steiner systems, even when restricted to the special case $S(n-1,n,k)$. Here is what is known (the information in the first three bullet points is all from the Wikipedia article on Steiner systems):

• When $n=3$, a Steiner triple system exists if and only if $k\equiv 1$ or $3\pmod 6$.

• When $n=4$, a Steiner quadruple system exists if and only if $k\equiv 2$ or $4\pmod 6$.

• When $n=5$, a necessary condition for a Steiner quintuple system of order $k$ to exist is $k\equiv 3$ or $5\pmod 6$, and $k\not\equiv 4\pmod 5$. They do exist for orders $11, 23, 35, 47, 71, 83, 107, 131, 167$ and $243$, but no general constructions are known.

• When $n=6$, the only known $6$-tuple systems (according to this website maintained by Dan Gordon) have orders $k=12, 24, 36, 48, 72, 84, 108 132, 168$ and $244$.

---

Furthermore, a successful strategy exists when $k=n+1$. Number the people $1$ to $n$ with person $n$ in back, number the colors $1$ to $n+1$, and let $h_i$ be the color on person number $i$ for $i\in \{1,\dots,n\}$. Furthermore, define $h_{n+1}$ to be the color missing from $\{h_1,\dots,h_n\}$. The person in back does not know the permutation $(h_1,\dots,h_n,h_{n+1})$, but he knows it is one of two possibilities. Furthermore, exactly one of these is even, and the other is odd. Player $n$ announces the value of which causes $(h_1,\dots,h_n,h_{n+1})$ to be an even permutation. This lets all subsequent players also guess their color.