Hat guessing without knowing the colors

Question

Generalization of this problem: Guessing hat colors. 4 prisoners

Suppose that there are $N$ prisoners, instead of $4$. Show, by finding explicitly the strategy, that if $N$ is even there is a strategy that allows prisoners to save themselves with certainty. Show instead that if $N$ is odd there is no strategy that allows prisoners to save themselves with certainty. However for the case $N$ odd, assuming that for each prisoner the hat's color is choosen with probability $1/2$, find the optimal strategy in this case.

Edit: For the second part of my question, if $N=2k+1$, I don't know if this is optimal but I can save them with probability

$$ \frac{ \binom{N}{k} + 2 \sum_{j=0}^{k-1} \binom{N}{j} }{2^N} = \frac{2^N - \binom{N}{k}}{2^N} = 1- \frac{\binom{N}{k}}{2^N} $$

Answer 1

If $N$ is even, then an easy strategy is as follows:

Every prisoner names whichever colour they see an odd number of hats of. In essence the prisoners assume that there are an even number of hats of each colour, and deduces their colour from that assumption. If the assumption is correct, all prisoners name the correct colour, and if the assumption is wrong all prisoners name the wrong colour. Either way, they will be freed.

For odd $N$ we have a problem. If a prisoner sees the same number of hats of each colour, they would need a a non-random consistent way to pick one colour over another. Possible methods could be:

Order the colours by name alphabetically.
Order the colours by the order in which they occur in the colour spectrum (assuming they have a hue).

Assuming that the prisoners have devised a method where every prisoner that sees two colours can consistently pick a preferred one they all agree on, then they can use the following strategy:

Every prisoner who sees only one colour, names that colour. Every prisoner who sees two colours, assumes that there are an even number of hats of their preferred colour and names their own hat colour accordingly.

If every prisoner sees two colours, they will all use the same assumption and all be correct or all be wrong. If all the hats are the same colour, the prisoners will all be correct. When there is exactly one hat of the preferred colour, then all the prisoners will be wrong. It is only when there is exactly one hat of the non-preferred colour that things go badly, as the single prisoner gets it wrong while the others get it right.
So in only $N$ out of $2^N$ cases do the prisoners fail to free themselves.

I believe this to be optimal, and offer the following arguments for it. Firstly, there can be no perfect strategy for odd $N$:

Consider a case where a prisoner sees $A$ white hats and $B$ black hats. A perfect strategy will determine what the prisoner says, and that should apply whether their hat is actually white or actually black. In one case they (and all the other prisoners) will be correct, and in the other case they (and all the other prisoners) will be incorrect. This means that when there are $A+1$ white hats the prisoners' answers will have the opposite truth value than when there are $A$ white hats.

If a prisoner sees only one colour, then there is only one colour they can name as they do not know the other colour. If all the hats are the same colour, the prisoners will therefore all name the correct colour.

If there are no white hats ($A=0$), the prisoners will all be correct. For one white hat ($A=1$) the truth value must be opposite in a perfect strategy, so the prisoners must all be wrong. As $A$ increases, the truth value keeps alternating in a perfect strategy so the prisoners are correct when $A$ is even and wrong when $A$ is odd.

This leads to a contradiction when $A=N$ is odd. In this case all hats are white, the prisoners have no choice but to say their hats are white and be correct, though a perfect strategy would need them all to be wrong. It works perfectly well when $N$ is even.

Given there is no perfect strategy, there must be a case where the prisoners fail.

The best we can do is have only one of the cases $A=0$, $A=1$, ..., $A=N$ fail, and have a perfect (alternating) strategy in all the other cases. The cases with lowest probability are $A=0$ or $A=N$, but we have no choice of strategy there. The next best we can do is have one of the cases $A=1$ or $A=N-1$ fail, and the strategy decribed before achieves that.

Answer 2

Note: Colors cannot really be sorted (if just seen). Whether that the reddish blue color is darker than that greenish blue one: hard to tell. Their names: unclear.
For this puzzle to makes sense though. We must assume every prisoner can discern the 2 colors and name them in a way such that the warden understands which of the 2 is meant.

Assuming there is no consistent way to pick one color over another:

Pick a leader beforehand.
Guess as if the least appearing hat color occurs an even number of times.
If this is unclear: Choose as if it is clear to the leader. (i.e. as if the leader is wearing the other color)

This only fails if the leader sees an equal amount of both hats.
success rate: $1- \frac{\binom{2k}{k}}{2^{2k}} $

Addition: Why is this optimal?

By assumption the colors cannot be sorted.
One way left to get a favorite color is to pick the color of a leader (or odd-numbered leader group)
However that group then does not know the favourite color used by the others, resulting in a 50% success when used at best.

Another way is to use the majority/minority color - 100% (i.e the maxmium) success is possible if no one sees both colors in equal number: Assume an even number of the minority color
- This cannot be used if both colors are seen in equal number.

Thus (only) with a k/k+1 split we need to use the leader (to make sure everone who sees k/k chooses the same.)
Obviously, this does not work if the leader sees k/k (since the leader cannot see their hat) thus when using a leader, the only workable option is to assume the leader sees k-1/k+1

Answer 3

Although the previous answers of @Jaap Scherphuis and my comment below need to compare colors, and hence colors need to be sorted, I tend to agree with @Retudin in the fact that colors are unlikely to be orderable (if just seen). Here is a way that I believe works without comparing colors that possesses probability of success of

$$ 1- \frac{N}{2^N}$$

I'm still not 100% sure that it works.

The general answer is

The optimal solution is given by constructing a winning set with maximal cardinality, and then each prisoners simply follows the arrows of the graph

The explanation of the solution and terminology

We can simply formalize the problem with a directed graph with $2^N$ vertices, where every vertices represents a possible combination of hats colors. Two nodes are connected with an edge if and only if the two corresponding combinations of hats differs by only one hat color. In this way for a prisoners observing the others hats mean to be on a edge connecting two different vertices and don't know in which direction to go. It is not difficult to see that every vertex is connected to $N$ different neighbors. Suppose that a prisoners see the vertices $v_j$ and $v_k$, meaning that depending on its hat color the arrangement of all hats is either $v_j$ either $v_k$, an arrow $v_j \rightarrow v_k$ is putted between the two connected vertices if this prisoner decide, in some way, that the color of his hat is such that the combination of all $N$ hat colors is the one corresponding to the vertex $v_k$. Let's make an example with $N=3$, the vertex $(0,0,0)$ is connected with an edge $(1,0,0)$. We put an arrow $(1,0,0) \rightarrow (0,0,0)$ and this mean that the first prisoner, that one observing $(0,0)$ decide to assume that his hat is also of color $0$ and so if whenever he will observe $(0,0)$ we will bet that their hat combination is $(0,0,0)$. It is clear from the fact that the prisoners don't know the colors that if a vertex correspond to a combination with only one color of type $0$ and $N-1$ colors of type $1$ (respectively only one hat of color type $1$ and $N-1$ colors of type $0$) then an arrow must exit from this node in the direction of the vertex with all colors of type $1$ (respectively pointing the vertex with all colors $0$). This constraint is the reason why with $N$ odd it is not possible, unlike the case $N$ even, to find a strategy that saves prisoners with certainty

Let fix some strategy $S$. We say that for a vertex $v_j$ the strategy $S$ is a winning strategy if all arrows point to its neighbors (meaning that each prisoner guess false) or if all arrows point to the vertex $v_j$ itself (meaning that each prisoner guess right). In other hands we say that for a vertex $v_j$ the strategy $S$ is a losing strategy if there is at least one arrow pointing the vertex $v_j$ and at least one arrow pointing one of its neighbors. We call winning set, the set containing all winning vertices.

It is clear that for $N$ odd cannot exist a winning strategy for every vertex. Assuming the contrary, if there exist a strategy $S$ for which every node is a winning strategy we necessarily have that all arrows connected to vertices $(0,0,\ldots,0) $ and $(1,1,\ldots,1)$ are pointing the vertices themselves, this is because the prisoners doesn't know the colors chosen by the warden. But we have that there exist a path of length $N$ (the number of edges) $(0,0,\ldots,0) $ to $(1,1,\ldots,1)$ an so we have found at least one losing vertex. Indeed we start with $$(0,0,0,\ldots,0,0) \leftarrow (1,0,0,\ldots,0,0) $$ and with $$ (1,1,1,\ldots,1,0) \rightarrow (1,1,1\ldots,1,1)$$ then we continue in this way $$(0,0,0,\ldots,0,0) \leftarrow (1,0,0,\ldots,0,0) \rightarrow (1,1,0,\ldots,0,0) $$ and $$ (1,1,\ldots, 1,0,0) \leftarrow (1,1,1,\ldots,1,0) \rightarrow (1,1,1\ldots,1,1)$$ we continue in this way and we notice that whichever way we put the $\left \lceil \frac{N}{2} \right \rceil$-th arrow we create a losing vertex. So it is impossible to have a strategy in which $N$ prisoners are saved with certainty.

It is simple to construct arrows in a such way that there are only $ \binom{N}{\left \lfloor N/2 \right \rfloor} $ losing vertices, and thus a strategy of success of $$ 1- \frac{\binom{N}{\left \lfloor N/2 \right \rfloor}}{2^N}. $$ For example with $N=3$ we start with $ (1,0,0) \rightarrow (0,0,0) \leftarrow (0,0,1) $ and $(0,0,0) \leftarrow (0,1,0) $. And $ (0,1,1) \rightarrow (1,1,1) \leftarrow (1,1,0) $ and $(1,1,1) \leftarrow (1,0,1) $ and from here we simply continue trying to maximize the winning vertex. So we see for example that if $(1,0,0)$ is a winning nodes then $ (1,1,0) \leftarrow (1,0,0)\rightarrow (1,0,1)$. From here we already deduce that $(1,1,0)$ and $(1,0,1)$ are losing vertices. The same for $(0,0,1)$. and we get the following winning set $\{(0,0,0),(1,1,1), (1,0,0),(0,1,0),(0,0,1) \}$ and the following losing set $\{ (0,1,1),(1,0,1),(1,1,0) \}$

Now if the real combinations of hat is the vertex $v_r$ then every prisoners will observe $v_r$ together with another vertices different for each one. If $v_r$ is a winning vertices they simply follow the arrow and they will survive either by all guessing their own color or all guessing their own color wrongly. If $v_r$ is losing vertices they gonna die following the arrows. The question is the follow: what is the maximal cardinality of a winning set? Clearly if we found the set containing the winning vertices with maximal cardinality then we maximizes the probability of survival and as a optimal strategy the prisoners can simply build this winning set and then follow the arrows. The answer of @Jaap Scherphuis needs the colors to be sortable in some way as well as my answer to his solution by adding the darker color, but at the same time these solution describes a way to create a winning set of cardinality $2^N - N$, hence as an optimal strategy they can simply choose in this way the arrows and the winning set and so we no longer need to compare colors since the very observation of colors and the assignment of arrow direction tells us which direction to go, and then which color to guess. They just need to agree on which color is $0$ and which color is $1$, and this I assume to be possible because otherwise how does the warden know whether they guessed their own color or not.