Infinitely many dwarves wearing hats of 2 colours

Question

I have heard of the puzzle with 100 or 10 dwarves wearing a hat of a color, either red or blue, and standing in a straight line, and having to guess the color of their own hat - it's quite easy.

The solution to save all dwarves or all dwarves minus the first one is fairly simple and relies on the fact that the number of dwarves is finite. So what would happen if you had an infinite number of dwarves standing in a straight line?

Every dwarf wears a hat of color either red or blue and sees the color of the hats of all the dwarves standing in front of him. There is explicitly a first dwarf, who has to start guessing the color of his hat and then the guessing proceeds with the next one in the line.

If a dwarf guessed correctly, it is freed; if he guessed wrong, it is fried. Every dwarf can hear the voice of all other dwarves without a problem. Everybody is only allowed to speak out either the color red or blue, but no further information.

Is there a possibility for all dwarves to be freed? Well, probably no.

But is it at least possible that only finitely many of them are killed?

EDIT: This is a mathematical puzzle. No loopholes.

Answer 1

This puzzle has been discussed on the Mathematics Stack Exchange as in this question: Prisoners Problem.

The solution given there (by Asaf Karagila):

Encode the colors into $0$ and $1$, and define the equivalence relation on $2^\Bbb N$, $\langle x_i\rangle\sim\langle y_i\rangle$ if and only if there is some $k$ such that for all $n\geq k$, $x_n=y_n$. Using the axiom of choice the prisoners pick a representative from each equivalence class.

In his turn, the $n$-th prisoner looks for the representative class fitting the string of hats he sees ahead, assuming that all hats up to him are blue. Since all the prisoners follow the same representative to guess their own color, it is guaranteed that after finitely many deaths, the representative and the fashionable selection of hats by the warden will agree, and everyone else will survive.

Note that since the Axiom of Choice is non-constructive, so is this solution and hence may not be practically useful for the dwarves in the question. There seems to be a fair bit of discussion on whether the Axiom of Choice is required. Well it was shown by Hardin and Taylor [Hardin, Christopher S.; Taylor, Alan D. An introduction to infinite hat problems. Math. Intelligencer 30 (2008), no. 4, 20–25] that there being no winning strategy is consistent with ZF (plus other axioms which don't imply the Axiom of Choice). So in that sense the Axiom of Choice is necessary for a winning strategy.

Answer 2

The solution is the following:

We define the notion of a class of infinite sequence of hats. All sequences in this class differ from each other by only a finite number of elements. There are an infinite number of classes, each containing a infinite number of elements.

Why? As differences between classes are of infinite length, there is an infinite number of possible distances, which means there is an infinite number of classes.

For each such class we select a "representative" which is a single element of the class (a single infinite sequence of hats). So suppose we have the class "infinitely alternating red and blue, with a finite number of non-alternating hats in the first 20 elements". We can set the representative to be:

EDIT: Apparently, after digging a bit, a good way to define the classes is:

Two sequences are equivalent if they are identical after a finite number of items

Choice of a representative can be easily defined as choosing the sequence where the differences appear at the beginning of the sequence and are lexicographically smaller.

For example, the sequence

rbrbrbrbrbrb...

And, the sequence:

r[r]rb[br]rbrbrb... ([] denotes mismatches)

is a member of that class. Each dwarf can see the infinite sequence of hats in front of it and can recognize the class. The dwarves can see the mismatches in front of them, but do not know if their own hat is not a mismatch.

But, the difference is finite, and a modification of the standard rules for guessing a finite sequence can be applied. The first dwarf says "red" if there is an odd number of hats that are different in the "sequence", compared to the "representative" (or "blue" if the mismatches are even). From there on, each dwarf has sufficient info to tell the colour of their hat.

Note that, the number of classes is infinite, however, since we are talking about infinite dwarves, I assume this is acceptable.

Finally, since the first dwarf "guesses", the first dwarf has a 50% chance of survival, all other dwarves survive.

Oh, and because of the infinite number of classes, this can be directly applied to the problem with an infinite number of colours.

Summary for the naysayers

• Two sequences are equivalent if they are identical after a finite number of items.

• Choice of a representative can be easily defined as choosing the sequence where the differences appear at the beginning of the sequence and are lexicographically smaller.

• As the sequence is infinite, and differences are finite, there exists an infinite subsequence, that can uniquely define the class of the sequence.

Answer 3

Refer to the following link. The one answer which is simple to understand is the High pitch and low pitch. Each dwarfs answers his hat color in either high pitch or low pitch depending on the next dwarfs hat whether its in Red or Blue color.

Answer 4

A solution that saves all the dwarves except (maybe) the first one. It is very similar to the one given by theosza, but it also mixes an idea used in the original problem with finitely many dwarves.

We partition $\{ 0,1 \}^{\mathbb{N}}$ with the equivalence $ (x_j)_{j \in \mathbb{N}} \sim (y_j)_{j \in \mathbb{N}}$ if and only if there exists $k \in \mathbb{N}$ such that forall $ n \geq k $ we have that $x_n=y_n$. Now with the axiom of choice, the dwarves choose a representative $\tilde{x} =(\tilde{x}_j)_{j \in \mathbb{N}}$ from each equivalence class. Now the first dwarf sees in front of him a sequence of $ (x_j)_{j \geq 1} $ and he knows the class of equivalence and hence the representative $\tilde{x}$, so he can determine a $k \in \mathbb{N}$ such that for all $n \geq k$ we have $x_n = \tilde{x}_n$. Now the representative and the real sequence of hats may differ only on finitely many hats, the first $k$ hats, the first dwarf sees $k-1$ hats and says "blue" if $x_n \neq \tilde{x}_n $ for an odd number of indices $1 \leq n \leq k-1$ and says "red" if $x_n \neq \tilde{x}_n $ for an even number of indices $1 \leq n \leq k-1 $. The second dwarf sees $(x_j)_{j \geq 2}$, he knows $\tilde{x}$ and he knows also if the representative and the sequences of hats differ from an even number or an odd number of hats (because he hears what the first dwarf said), so he can deduce the color of his hat, i.e. he can deduce if either $x_1 = \tilde{x}_1$ or $x_1 \neq \tilde{x}_1$. The third one knows $\tilde{x}$, he sees $(x_j)_{j \geq 3} $, he knows also $x_1$ and he can deduce $x_2$ thanks to the first dwarf. Inductively we continue in this way, the $n$-th dwarf sees $(x_j)_{j \geq n}$, he knows the representative $\tilde{x}$, he knows $(x_j)_{1 \leq j \leq n-2}$, and thanks to the first dwarf he can deduce his hat, i.e. if $x_{n-1}$ is equal to $\tilde{x}_{n-1}$ or differs from $\tilde{x}_{n-1}$. So all the dwarves, except maybe the first one, guess correctly because they all follow the same representative $\tilde{x} $.

Answer 5

I was wondering if a dwarf with infinite range of sight can identify repeating pattern(s)?

What if there is only one single pattern that is infinite? This would mean the dwarfs can't be saved :(

Due to the fact that the number of dwarfs is infinite, there must be a repeating pattern at some point (this is almost too complicated for me now!). With infinite sight, every dwarf can find his own position within the repeating pattern (which can be very, very, very long).

Having said that, a dwarf can never be sure whether he really identified a pattern correctly since the number of dwarfs is infinite and he would have to see all dwarfs at once in order to be sure - which is impossible due to "infinite number",... I think?