# Infinitely many dwarves wearing hats of 2 colours

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.

• I think you should specify that the dwafs are facing the "infinite" direction. More specifically, that the dwarfs can be labeled by natural numbers, where each dwarf sees the dwarfs greater than it.
– xnor
Commented Jan 12, 2015 at 9:07
• Are they allowed to discuss any kind of strategy before they go into this situation? Commented Jan 12, 2015 at 9:16
• Is this what you are searching for?
– dmg
Commented Jan 12, 2015 at 9:17
• I'm a little lost. What happens if every dwarf is wearing the same color hat? Or the colors are in a ratio of 7:3? Do there need to be an even number of blue and red hats? Commented Jan 12, 2015 at 14:43
• Would you please pick a consistent terminology for directions? First you say "in front of", then you say "first" and then "next in line". It's all unnecessarily confusing to someone who doesn't already know what you're talking about. Also the first sentence is quite a muddle to someone who is not already familiar with the problem, and you quickly lead into a spoiler for it as well (well, it might be a spoiler, as soon as someone figures out what you mean by the first problem). How about trying to restructure the whole thing in a clear non-spoiler way? Commented May 30, 2019 at 11:06

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.

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.

• There is discussion at: chat.stackexchange.com/rooms/20187/… Commented Jan 12, 2015 at 16:25
• Whoops, sorry, I tried to move the comments to chat, purged all the comments, and then realized I couldn't undelete my comment with the chatroom link on mobile. My bad; thanks for finding it. Commented Jan 12, 2015 at 16:31
• I think you should mention that the axiom of choice is being used to pick the representative elements. You can't choose the lexicographically smallest element of the class, as there may be no minimum like for rrrrrr... . There is no constructive algorithm to find representatives.
– xnor
Commented Jan 12, 2015 at 19:07
• How do we choose the class? It is because each dwarf is preceded by a finite number of dwarfs, and therefore can always see the class after him? Commented Jan 12, 2015 at 19:38
• Anyway, this answer is a bit like solving a puzzle "I have one ball and a knife. I need two balls. How do I get them?" by appealing to the Banach-Tarski dissection. Perfectly reasonable as long as the puzzle is about surprising consequences of the axiom of choice, not about actual balls cut up with actual knives. The answer makes a point, but the point is not about what dwarfs in hats can do, it's about uncountable infinities. Commented Jan 13, 2015 at 13:53

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.

• Well that's certainly got the merit of simplicity!
– A E
Commented Jan 12, 2015 at 13:42
• The linked question is explicitly about the finite case; and your answer, while clever, isn't really satisfying: the intent is clearly that each dwarf can communicate only one bit to the neighbor in front of him. Commented Jan 12, 2015 at 14:30
• They could impart several bits, if required: high/low, loud/quiet, fast/slow - and remember that humans (and presumably dwarves) are not binary - we can at the very least differentiate three (high/normal/low, fast/normal/slow, loud/normal/quiet) levels for each of these measurements. I make that a minimum of 27 bits even assuming that three levels per measurement is as as fine grained as we can get, that there is only one word and there are no other ways to inflect the word. Commented Jan 12, 2015 at 17:11
• No, this is wrong. The dwarves can only call out a hat color, they can't do it in different pitches. Commented Jan 12, 2015 at 17:14
• Says who? I don't see that in the rules Commented Jan 12, 2015 at 17:15

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}$$.

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?

• There can be an infinite sequence which does not have a repeating pattern. For example rbrrbbrrrbbb...
– dmg
Commented Jan 13, 2015 at 7:53
• @dmg (read the <strike>'deleted'</strike> line). You are right, but it is infinite and 'infinite' includes the guarantee of a repeating pattern somewhere. I think this is a matter of definition? Commented Jan 13, 2015 at 8:12
• PI is an example of a non-repeating infinite pattern.
– dmg
Commented Jan 13, 2015 at 8:29
• The brain doesn't really handle infinity well :) Just look at Cantor
– dmg
Commented Jan 13, 2015 at 8:40
• @bobbee: ah, yes, watching the best monkey out of an infinite number of monkeys play chess is awesome. I was referring to watching one monkey play chess ;-) Commented Jan 13, 2015 at 13:45