1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila Oct 2 '18 at 7:44
  • 1
    $\begingroup$ 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? $\endgroup$ – Asaf Karagila Oct 2 '18 at 7:48
  • $\begingroup$ 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"? $\endgroup$ – bof Oct 2 '18 at 8:03
  • $\begingroup$ @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. $\endgroup$ – Asaf Karagila Oct 2 '18 at 8:15
  • $\begingroup$ @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? $\endgroup$ – penguin_surprise Oct 2 '18 at 8:19
0
$\begingroup$

Fascinatingly, the "easiest" case is when H is not merely infinite but uncountably infinite.

Namely, if H becomes uncountably infinite, the number of prisoners can scale up to countably infinite without breaking the problem at all. This is because the set of all sequences of real numbers has cardinality equal to that of the real numbers themselves, meaning that once you've assigned all (uncountably infinite) colors to real numbers, you can create a bijection from the reals to every single sequence of reals. This way, when the person in the back announces a color, everyone in front of them immediately knows their own hat color before anyone else must announce anything at all because the sequence itself was fully encoded in the color the person announced. This assertion does not rely on the axiom of choice in any way.

When H is countably infinite, this indeed becomes more of a "sum and subtract" game as indicated in the original quote in a fairly easy-to-understand way that also does not require choice (let's ignore my previous note about countably many prisoners and only focus on the finitely many prisoners presented in the actual problem).

When H is finite, you can just perform a standard modulus for the sum (that is, modulo |H|).

You seem to be imagining the axiom of choice as necessary for the warden to select hats to place in the first place, but that... simply isn't a relevant part of the problem? The interest lies in the solution, not the problem statement. The problem statement doesn't change even if the actual hats were chosen long in advance: the prisoners are merely presented with their potential hat colors in advance.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.