Modified hat problem seems hard

Question

I found the following problem on instagram:

Seven prisoners are given the chance to be set free tomorrow. An executioner will put a hat on each prisoner's head. Each hat can be one of the seven colors of the rainbow and the hat colors are assigned completely at the executioner's discretion. Every prisoner can see the hat colors of the other six prisoners, but not his own. They cannot communicate with others in any form, or else they are immediately executed. Then each prisoner writes down his guess of his own hat color. If at least one prisoner correctly guesses the color of his hat, they all will be set free immediately; otherwise they will be executed. They are given the night to come up with a strategy. Is there a strategy that they can guarantee that they will be set free?

Now, generalizing this for n people and n hats, the usual solution involves coding each color with a number in Z/nZ and for the ith person to calculate what it's hat color should be if the sum of all colors was equal to i. More information here: (Rainbow Hats Puzzle).

I, however, didn't really like this solution because each person is using the information of its own personhood (it's i value) as well as what they can see in the circle. In other words, the "strategy" is a function of each color the person is seeing as well as of which person it is: f(c1,...,c_(n-1) , i).

I was wondering if, by not allowing the last variable it is still possible to solve it (meaning the strategy must not differentiate each individual but depend only on the colors that are seen). I think it isn't and managed to prove by hand that n = 2 and n = 3 are impossible.

My first try to attack this problem so far has been to consider some special cases to gain information about f and try to achieve a contradiction. For example, it's easy to see that f(c,c,...,c) = c ( if all the colors a person sees are equal, the strategy must involve them saying that color ). My second try was a counting argument but i don't really know combinatorics so my ideas were limited.

Anyone has any idea on how to solve this?

Answer 1

Here is a probabilistic argument.

Suppose the executioner decides to allocate the hat colours uniformly at random with replacement, i.e. with $n^n$ equally likely possible allocations.

Then the probability an individual prisoner's guess as to their own colour has probability $\frac1n$ of being correct, and the expected number of correct guesses is $1$.

If there is a non-zero probability that two or more guesses are correct then there must also be a non-zero probability that no guesses are correct, which prevents the guarantee.

So no prisoner can adopt a strategy which has any randomness in response to the colours seen.

Nor can two prisoners adopt identical strategies, since there is a non-zero probability that they both see the same pattern of colours on others.

So any overall strategy providing the guarantee must require distinct individual response strategies for different prisoners, so each response depends on the individual answering. The linked answer to this question is an example of such distinct strategies and it works, though there may be other possibilities that also work.

Answer 2

If the prisoners can't use any numerical identification of themselves in choosing their strategy, then each prisoner's choice can only depend on the multiset of colours that he or she sees. In other words, if $\ f\ $ is the function representing the prisoners' choices, then $\ f\big(c_1,c_2,\dots, c_{n-1}\big)=$$\,f\big(d_1,d_2,\dots,d_{n-1}\big)\ $ whenever $\ \big\{c_1,c_2,\dots, c_{n-1}\big\}\ $ and $\ \big\{d_1,d_2,\dots,d_{n-1}\}\ $ are equal as multisets. For such a function to guarantee the prisoners' freedom it must satisfy the following condition:

For every multiset $\ S\ $ of cardinality $\ n\ ,$ of the available colours, there exists at least one $\ c\in S\ $ such that $$ f(S\setminus {c})=c \label{e1}\tag{1}$$

Call such a function a survival function.

Suppose $\ f\ $ is a survival function. As you've already deduced, it must satisfy $$ f\big(\big\{c^{n-1}\big\}\big)=c\ . $$ Now if the prisoners adopt $\ f\ $ for their strategy, $\ n-1\ $ of them are assigned the same colour, $\ c\ ,$ and the remaining one assigned the colour $\ d\ne c\ ,$ then the colour chosen by this latter prisoner will be $\ f\big(\big\{c^{n-1},d\big\}\setminus\{d\}\big)=$$\,f\big(\big\{c^{n-1}\big\}\big)=$$\,c\ ,$ while all the other prisoners, with $ c$-coloured hats, will choose the same colour $\ f\big(\big\{c^{n-1},d\big\}\setminus\{c\}\big)=$$\,f\big(\big\{c^{n-2},d\big\}\big)\ .$ Since the prisoner with the $\ d$-coloured hat will have nominated the wrong colour, $\ c\ ,$ for his or her hat, then for $\ f\ $ to be a survival function, we must have $\ f\big(\big\{c^{n-2},d\big\}\big)=$$\,c\ .$ By repeating this argument with successively larger multisets $\ D\ $ with $\ c\not\in D\ ,$ we can show by induction that for any such non-empty multiset of cardinality $\ r\le n-3\ $, $\ f\big(\big\{c^{n-r-1}\}\cup D\big)=$$\,c\ .$ However, for $\ n\ge5\ $ this would require both $\ f\big(\big\{c^2,d^{n-3}\big\}\big)=$$\,c\ $ and $\ f\big(\big\{c^2,d^{n-3}\big\}\big)=$$\,d\ $ for any pair of colours $\ c,d\ $ with $\ c\ne d\ ,$ which is clearly impossible. Thus, there doesn't exist a survival function for $\ n\ge5\ .$ For $\ n=4\ $ it would require $\ f\big(\big\{c^2,d^2\}\setminus\{d\}\big)=c\ $ and $\ f\big(\big\{c^2,d^2\big\}\setminus\{c\}\big)=d\ ,$ so $\ f\ $ would fail the condition (\ref{e1}) for the multiset $\ S=\big\{c^2,d^2\big\}\ $ and therefore not be a survival function. Thus, there doesn't exist a survival function for $\ n=4\ $ either.

Since you've already proved that there's no survival function for $\ n=2\ $ and $\ n=3\ ,$ I haven't bothered trying to extend the above argument to cover those cases.

Analysis of Alternative Interpretation

$\def\ed{\stackrel{\text{def}}{=}}$ From your comment below, it appears that I've misunderstood what you're asking for. As I now understand it, you want to allow the prisoners to use a method in which each of them can assign $\ n-1\ $ indices to the colours they see in such a way that every prisoner who sees the same number, say $\ q\ $, of any given colour assigns the same set of $\ q\ $ indices to that colour, and those $\ q\ $ prisoners who see only $\ q-1\ $ occurrences of that colour each assign a different subset of cardinality $\ q-1\ $ of that same set of $\ q\ $ indices to that colour. If that understanding is correct, then I think you need to be rather more careful in specifying the restrictions on how the prisoners can actually implement the method. Otherwise it's easy to devise ways in which they can smuggle the standard solution into their implementation.

Suppose, for instance, the prisoners decide that they'll gather in a circle, assign the index $\ 1\ $ to the prisoner nearest the executioner (or some other landmark in the room), the index $\ 2\ $ to the prisoner on prisoner $\ 1$'s left, the index $\ n\ $ to the prisoner on prisoner $\ 1$'s right, and so on around the circle. They will all then have constructed the same bijection between the prisoners and the set of indices $\ \{1,2,\dots,n\}\ ,$ and can therefore use it to implement the standard solution.

In one of your comments above, you appear to be suggesting that a survival function ought to be defined as follows:

Let $\ C\ $ be the set of colours. A survival function is a function $\ f:C^{n-1}\rightarrow C\ $ such that for every $\ c\in C^n\ $ there exists $ i\in\{1,2,\dots,n\}\ $ such that $$ f\big(c^{<i>}\big)=c_i\ ,\tag{2}\label{e2}$$where$$c^{<i>}_j=\cases{c_j&if $\ j\le i$\\c_{j+1}&if $\ j\ge i+1$}$$

It's possible to adapt the argument used above to show that a survival function of this type can't exist either. Actually, even if such a function did exist, it seemed to me than any method I could think of for the prisoners to use it to effect an escape could be adapted to allow them to implement the standard solution. Since any conclusion whatever can be validly drawn from a provably false premise, however, it's not clear whether this observation really is true, or means very much, even if it is.

In the following argument I'll use the notation $\ c_1^{r_1}c_2^{r_2}\dots c_k^{r_k}\ $ to represent an $\ n$-tuple $\left(\text{if $\ \sum_\limits{j=1}^kr_k=n\ $}\right)$ or $\ (n-1)$-tuple $\left(\text{if $\ \sum_\limits{j=1}^kr_k=n-1\ $}\right)$ of colours according to the following definition $$ \big[c_1^{r_1}c_2^{r_2}\dots c_k^{r_k}\big]_i\ed\cases{c_1&if $\ i\le r_1$\\ c_j&if $\ \sum_\limits{\ell=1}^{j-1}r_\ell<i\le\sum_\limits{\ell=1}^jr_\ell$ \\ c_k&if $\ \sum_\limits{\ell=1}^{k-1}r_\ell<i\ .$} $$

Suppose now that $\ f\ $ is survival function in this second sense. Then, again, as you've already concluded, $$ f\big(c^{n-1}\big)=c\ . $$ Now, if $\ b\ne c\ $ then \begin{align} f\big(\big(bc^{n-1}\big)^{<1>}\big)&=f\big(\big(c^{n-1}b\big)^{<n>}\big)\\ &=f\big(c^{n-1}\big)\\ &=c\hspace{4em}\text{ from above}\\ &\ne b\\ &=\big[bc^{n-1}\big]_1\\ &=\big[c^{n-1}b\big]_n\ . \end{align} Thus, since $\ f\big(\big(bc^{n-1}\big)^{<1>}\big)\ne\big[bc^{n-1}\big]_1 \ ,$ then for condition $(\ref{e2})$ to hold there must be $\ j\in\{2,3,\dots,n\}\ $ such that \begin{align} f\big(\big(bc^{n-1}\big)^{<j>}\big)&=\big[bc^{n-1}\big]_j\\ &=c\ , \end{align} and since $\ \big(bc^{n-1}\big)^{<j>}=bc^{n-2}\ $ for all $\ j\in\{2,3,\dots,n\}\ ,$ it follows that $\ f\big(bc^{n-2}\big)=c\ .$ Likewise, since $\ f\big(\big(c^{n-1}b\big)^{<n>}\big)\ne$$\,\big[c^{n-1}b\big]_n\ ,$ then there must be $\ j\in\{1,2,\dots,n-1\}\ ,$ such that $\ f\big(\big(c^{n-1}b\big)^{<j>}\big)=\big[c^{n-1}b\big]_j=c\ ,$ and therefore $\ f\big(c^{n-2}b\big)=c\ .$

Now suppose that $\ 1\le s\le n-3\ ,$ and $\ f\big(b^rc^{n-1-r}\big)=c\ $ for all $\ r\le s\ .$ Then $\ f\big(\big(b^{s+1}c^{n-s-1}\big)^{<j>}\big)=f\big(b^sc^{n-s-1}\big)=c$$\,\ne \big(b^{s+1}c^{n-s-1}\big)_j\ $ for any $\ j\in\{1,2,\dots,s+1\}\ .$ Therefore, for (\ref{e2}) to hold, there must exist $\ j\in\{s+2,\dots,n\}\ $ such that $\ f\big(\big(b^{s+1}c^{n-s-1}\big)^{<j>}\big)=f\big(b^{s+1}c^{n-s-2}\big)=$$\,\big(b^{s+1}c^{n-s-1}\big)_j$$\,=c\ .$ It follows by induction that $\ f\big(b^sc^{n-1-s}\big)=c\ $ for all $\ s\in$$\,\{1,2,\dots,n-2\}\ .$ Likewise, we can apply the same argument to the $\ (n-1)$-tuples of the form $\ c^{n-1-s}b^s\ $ to conclude that $\ f\big(c^{n-1-s}b^s\big)=c\ $ for all $\ s\in$$\,\{1,2,\dots,n-2\}\ .$

The same arguments can obviously also be applied with the colours $\ b\ $ and $\ c\ $ swapped to obtain \begin{align} f\big(c^sb^{n-1-s}\big)&=b\hspace{4em}\text{and}\\ f\big(b^{n-1-s}c^s\big)&=b\ \end{align} for all $\ s\in$$\,\{1,2,\dots,n-2\}\ .$ But this now produces a contradiction for any $\ n\ge3\ ,$ because we require both \begin{align} f\big(bc^{n-2}\big)&=c\hspace{4em}\text{and}\\ f\big(bc^{n-2}\big)&=b\ . \end{align}