Enigma : of Wizards, Dwarves and Hats
I've got quite a hard enigma that require extensive knowledge in mathematics, and I thought some might appreciate it.
An evil sorcerer holds in prison an infinite number of dwarves (countably infinite). He gathers them and tells them : Tomorrow, I will align you so that the first of you will see all the other dwarves. The second one will see all of them but the first, etc... Then, I will put a hat on each of your heads, black or white. No one can see his own hat, or the hat of those before him. But each dwarf can see the hats of those after him (they've got a good eyesight). And then, beginning with the first dwarf, I will ask each of you to tell me exactly one word, "Black" or "White". But you will have to whisper it in my ear, so that no one else can hear it. Then, when it's done (the sorcerer is quite fast) I'll release the dwarves who rightly guess the color of their hat and keep the rest imprisonned.
The dwarves gather after the meeting, and they find a strategy so that only a finite number stay imprisonned. What did they decide?
P.S : There is no trick. There is no information given from one dwarf to the other when they say "Black" or "White" to the sorcerer. They don't grunt or wait a certain time. The dwarves can't escape or do anything fishy.
However, the math involve some... ambiguous math =)
Spoiler warning: This is a fun puzzle -- solution follows; don't read on if you want to try it yourself :-)
The dwarves, being rather pensive types, reflect deeply upon their predicament. Having been imprisoned for a long (infinite?) time, they realize that they can only liberate themselves externally if they first liberate themselves internally. They mustn't let their long captivity rob them of their inner freedom. Despite having been incarcerated for as long as they can remember, they realize that they can only escape if they truly believe that they have a choice. And so they embrace the axiom of choice.
Using the axiom of choice, they choose (beforehand) one representative from each class of (countably) infinite binary sequences under the equivalence relation that relates all sequences that differ only in finitely many places. Then each dwarf determines the equivalence class of the actual hat assignment and guesses that s/he is wearing the hat specified by the representative chosen for that class.
Note: This is for the version when the dwarves can hear what the others have said.
1)
For infinite tuples $(d_1, d_2, \dots )$, with each coordinate $d_i$ being Black/White, the dwarves agree upon the representatives for each class of the equivalence relation: $x$ related to $y$ if and only if $x$ and $y$ differ in a finite number of positions.
They also agree that Black = even and White = odd.
The first dwarf calls out the parity of the number of positions the tuple formed by the rest of the dwarves, differs from the representative of the class to which that tuple belongs.
2)
A possibly different proof is that the infinite graph formed by the tuples (two tuples being adjacent iff they differ in exactly one position) is $2$-colourable. The dwarves agree upon a colouring of the graph and the first dwarf calls out the colour of the vertex corresponding to the tuple formed by the rest of the hats.
That the graph is $2$-colourable follows from Erdos' wonderful theorem (proved using compactness arguments) that an infinite graph is $k$-colourable iff every finite sub-graph is.