# Hat-guessing problem for finitely many prisoners and infinite sets of hat colors and the Axiom of Choice

In the "easy" version of the hat-guessing problem, there are n prisoners (say, 100) facing forward in a line, wearing hats with colors from a set $$H$$ in a sequence decided by the warden. Each can only see the hats of those in front of them. The prisoners try to guess, in order, their own hat color, taking into account what they can see and all previous guesses, and each prisoner gets to go free if they guess correctly. It's well-known that for $$|H| = 2$$, there is a strategy so all but the first go free, which works for any finite number of colors.

In the "hard" variant, there are $$\omega$$ prisoners, who do not get to hear any previous guesses, but famously if choice holds they have a strategy where all but finitely many go free.

However, for a variant of the easy version of the problem, I came across the following statement:

Its interesting to notice that a larger number of hat colors poses no problem here. For any set of hat colors $$H$$, the prisoners can pick an abelian group structure on $$H$$. Then, the first prisoner guesses the ‘sum’ of all the hat colors he can see. The next guy can then subtract the sum of the hat colors he sees from the hat color the first guy said to find his own hat color.

$$H$$ is not said to be finite, and the existence of a group structure (or even cancellative magma) on every non-empty set is equivalent to choice, which ordinarily wouldn't be a problem except that the article seems to imply otherwise, which raises the interesting question of whether a modified version of this statement can hold without choice. Implementing this strategy by the prisoners (I think) also only requires a cancellative magma on $$H$$, but I'm not sure, in either case, if only one-sided cancellative suffices. In any case, does the existence of any equally successful alternative strategy at all for all possible $$H$$ require choice, and how much? In $$ZF+ \neg C$$, given any $$H$$ is there a strategy so that for any sequence of $$n$$ hat colors from $$H$$, all but one guesses correctly?

• The statement makes no sense if $H$ is infinite. What is the sum of infinitely many elements of a group? Even if the group is $\Bbb R$ and you have a convergence of some sums, you'd still be summing uncountably many colors. – Asaf Karagila Oct 2 '18 at 7:44
• There used to be a saying about the Technion university, which trains excellent engineers, that they asked their students to design a pipe that transfers 1000 cubic meters of blood between two cities in Israel. They all did it perfectly, but nobody asked where the blood is coming from, or why you would use it. It was used as a reason to introduce some humanities and social sciences into science and engineering curriculum, which is fine. But it is also a parable about looking up from the definitions and at the bigger picture. What does it even mean "sum all colors" in an infinite group? – Asaf Karagila Oct 2 '18 at 7:48
• In the game with $\omega$ prisoners, does prisoner $n$ see prisoners $0,1,2,\dots,n$ or does he see prisoners $n+1,n+2,n+3,\dots$? Which way is "forward"? – bof Oct 2 '18 at 8:03
• @bof: The standard way, I think, is that you see the tail. Otherwise the first prisoner sees nothing and has to guess, so the information the first guy relays to the rest is pure guesswork. – Asaf Karagila Oct 2 '18 at 8:15
• @AsafKaragila: I get what you're saying about infinite sums not making sense in groups, but I must have missed how they come in? I'm meaning to ask about only finite sets of n prisoners, where the set of possible hat colors H is infinite. Why does that lead to summing infinitely many elements? – penguin_surprise Oct 2 '18 at 8:19