# Generalization of a certain riddle and ultrafilters (?)

I was once told the following riddle: 100 dwarfs stand in a straight line, each wears a hat of the colour red, yellow or green and they can see only the hats of the dwarfs in front of them. A dwarf will be released, if he can guess the colour of it's hat correctly and he is only allowed to speak once. If he cannot guess the colour correctly, he dies. And of course each dwarf can hear all the other dwarfs clearly. The question is: Which strategy should the dwarfs use so that as many as possible can be saved.

This riddle is not too difficult, so the riddle was generalized so that, there are infinite many dwarfs. And the question now is, how many dwarfs can be saved and how? I was also told that you can save all apart from a finite amount of dwarfs and that using ultrafilters leads to success. I don't know, whether this is true or not, (but I strongly think it is). I would really like to see and then understand the answer to that riddle. I would be really happy, if someone can help me.

• For much more than you may want to know, please see this. I also remember reading a nice article in Mathematical Intelligencer, don't remember when or the author(s). – André Nicolas Oct 15 '14 at 9:29
• @AndréNicolas: Same authors – see this MO question which (curiously enough!) also appeared today: mathoverflow.net/questions/184425/… – Hans Lundmark Oct 15 '14 at 17:13
• I have no idea what I should think about this coincidence. Joonas Ilmavirta post however far better and more interesting than mine and thx for the answers. I found several articles now on the internet dealing with similar problems etc. – Imago Oct 15 '14 at 17:21

## 1 Answer

Assuming the dwarves are numbered by the natural numbers in order of speaking, that the dwarves believe in the axiom of choice, and that they have excellent memory, they can proceed as follows. They consider all possible configuration of hat colours. This can be modeled by all functions $f:\mathbb N \to C$, where $C$ is the set of colors (assumed finite, not necessarily $3$). They then define an equivalence relation on all configurations by stating that $f\sim g$ when $f$ and $g$ agree almost everywhere (i.e., differ only on finitely many values). Then they invoke the axiom of choice to choose a representative of each equivalences class and they all memorize the chosen representatives.

Now, when they are asked in turn to speak and state a color, they each do the following. Looking at all dwarves ahead, the dwarf to speak compares that information and finds the unique representative of that equivalence class (this is possible because the only information the dwarf is missing is a finite portion of the configuration). The dwarf then speaks out the color in his/her position as appearing in that memorized representative.

You can now show that only finitely many dwarves will get their hat color wrong. Note also that no passing of information is actually required. Thus, in fact, this riddle generalizes further by requiring all dwarves to speak simultaneously, but for uncountable cardinalities dropping the condition that they are well-ordered and only see the next dwarves, and instead all dwarves see all other dwarves. Also, the cardinality of the dwarves is irrelevant. Using this strategy only finitely many dwarves will be wrong.