# 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). Oct 15, 2014 at 9:29
• @AndréNicolas: Same authors – see this MO question which (curiously enough!) also appeared today: mathoverflow.net/questions/184425/… Oct 15, 2014 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. Oct 15, 2014 at 17:21

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.