An infinite set of prisoners {#1, #2, #3, ...}, are each given a colored hat and can see hats in front of them: #j sees #(j+1), #(j+2), ... With no information except his location (#j), and the hats he can see, and any strategy discussed the night before with his fellows, each prisoner tries to guess his own hat color.
Devise a strategy that guarantees that only a finite number of prisoners will misguess. You should assume the Axiom of Choice.
~ ~ ~ ~ ~ ~ ~ ~
SOLUTION:
Write 'a' or 'b' to denote an infinite sequence of hat colors:
a = a
1a
2a
3a
4 ...
b = b
1b
2b
3b
4 ...
Write a ≈ b to denote that a and b differ at only a finite number of points.
If a is the actual correct sequence (a
j is the hat color of prisoner #j) and b is the sequence of guesses, then the prisoners succeed if and only if a ≈ b.
Note that a ≈ b and b ≈ c imply that a ≈ c. This makes '≈' an
equivalence relation. This relation partitions the set of all sequences into an uncountable number of equivalence classes. Each prisoner (#j) observes all but a finite number of hats (#1, #2, ..., #j) and therefore knows which equivalence class contains the actual sequence. Only one such class fits; that class will be the same for all prisoners.
During their consultations the night before, prisoners have agreed on a CHOICE function: For each equivalence class, they have assigned a particular representative sequence. For example, suppose they assigned 'b' as the representative of the class containing 'a.' The prisoners simply guess their hat color according to 'b.' Since a ≈ b, they succeed.
Q.E.D.
Here is one write-up on the problem. That article mentions that the solution works even if the number of prisoners and/or the number of hat colors is uncountable. It shows, at least for the countable case, that the number of misguesses can be reduced to just one at the most, if prisoners can hear earlier guesses.
~ ~ ~ ~ ~ ~ ~ ~ ~
I realize that I botched the presentation of this puzzle in at least two important ways. I am hugely embarassed.
Major apologies to all. Give yourselves full credit if you were misled by my mistakes.
I don't know what excuses to offer — (personal crises? creeping senility?) — but I should refrain from attempting presentations of this complexity in future.