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 =)

• I think this falls under "there is no actual problem to be solved" section of math.stackexchange.com/faq - in particular, you already know the answer, and anyone else who wants to can google it. – Zev Chonoles Apr 22 '11 at 17:22
• You may want to add that the dwarves need to have absolutely perfect eye sight with infinite resolution and an uncountably infinite capacity to process what they see. – Eric Nitardy Apr 22 '11 at 17:24
• @Qiaochu: I'm relatively new here, so I don't pretend to understand the scope of the site, but I'd like to. The FAQ says "We welcome questions about [...] Solving mathematical puzzles" and "It’s also perfectly fine to ask and answer your own question". Are you saying that it's the combination of the two that makes this off topic? – joriki Apr 22 '11 at 18:56
• @joriki: This meta thread is relevant and shows some examples. We can always vote to reopen, I have no opinion here, but I would support it if you ask me to. – t.b. Apr 22 '11 at 19:17
• Perhaps some elaboration on policy should be added to the meta thread meta.math.stackexchange.com/questions/1190/…. I'm also not sure what makes this off topic, and I'm voting to reopen. – Jonas Meyer Apr 22 '11 at 19:20

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.

• Is the number of sequences modulo that equivalence really countable? I thought that each class is countable, but the total number of sequences is uncountable, therefore the number of classes should be uncountable as well. – Myself Apr 22 '11 at 17:31
• @Moron: I think the answer you deleted was quite interesting, even though it is in fact an answer to a slightly different question. – Myself Apr 22 '11 at 17:48
• @Myself, @Moron: I agree -- it makes the puzzle even more amazing that all but one can be saved in that case -- I thought a finite number was already counterintuitive enough :-) – joriki Apr 22 '11 at 17:50
• This answer has always left a bitter after taste for me. The axiom of choice says that there exists a set containing one element from each of the sets. But it doesn't actually give you an algorithm to construct this set. Indeed, if there was an algorithm, no axiom would be needed. So I never understand what people mean when they say "using the axiom of choice, they choose...". Just because somebody tells me that there are several hundred thousand species of insects on earth doesn't mean that I can name them or put them in an order or do anything meaningful with them, really. – Alex B. Apr 23 '11 at 5:20
• @Alex: On a more philosophical level, the dwarves aren't computers. Who says they need an algorithm to do things? If you're willing to believe they have uncountable processing power and uncountable memory, (and, for that matter, that there are sorcerers and dwarves), why not believe that they can intuit a set of representatives? Now you might argue that if they can do that, anything is possible and the problem becomes arbitrary. But I don't think so -- you can make a distinction between intuiting mathematical objects and intuiting the state of the external world -- they can't do the latter. – joriki Apr 23 '11 at 6:03

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.

• I also seemed to remember that is somehow involved parity, but it turns out it's actually easier to just use the representative directly. Also I don't think the parity will help decrease the finite number of dwarves that stay behind? – joriki Apr 22 '11 at 17:32
• @joriki: Yes, with parity, no more than one stays imprisoned. – Aryabhata Apr 22 '11 at 17:35
• I believe the problem statement precludes any communication once the dwarves decide on a strategy or, at least, that is the intention behind the questioners P.S. section. – Eric Nitardy Apr 22 '11 at 17:35
• @Eric: Thanks for pointing that out. I missed the "whisper in my ear" part. – Aryabhata Apr 22 '11 at 18:00
• The connected components of the graph in 2) are precisely the equivalence classes in 1), so given a set of representatives of the equivalence classes, there's a bijection between the colourings of the graph and the choices of parity for the representatives. So if you let the assignment of black and white to even and odd in 1) depend on the equivalence class, the two strategies are equivalent. – joriki Apr 22 '11 at 18:15