12
$\begingroup$

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

  • 3
    I think this falls under "there is no actual problem to be solved" section of http://math.stackexchange.com/faq - in particular, you already know the answer, and anyone else who wants to can google it.2011-04-22
  • 0
    I first learned about this problem on this blog: http://cornellmath.wordpress.com/2007/09/13/the-axiom-of-choice-is-wrong/ , following a link from a MO-answer or comment I think.2011-04-22
  • 2
    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.2011-04-22
  • 0
    Closed. math.SE is not for asking puzzle questions that you already know the answer to.2011-04-22
  • 8
    @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?2011-04-22
  • 1
    @joriki: [This meta thread](http://meta.math.stackexchange.com/questions/1839/questions-whose-answers-are-known-to-the-op) 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.2011-04-22
  • 4
    Perhaps some elaboration on policy should be added to the meta thread http://meta.math.stackexchange.com/questions/1190/is-math-puzzle-on-topic-or-off-topic. I'm also not sure what makes this off topic, and I'm voting to reopen.2011-04-22
  • 1
    I've also voted to reopen, for several reasons: In the thread @Theo links to, 18:8 votes were for answers saying asking questions you know the answer to is OK. Especially relevant are the answers by Carl, which shows that the software was specifically modified to allow accepting one's own answer, and by vonjd, who wrote "It could even be that there is a new way shown how to arrive at the solution - or even a generalisation and/or new connection. So if the question is valid and interesting everybody will learn." I'd say that's exactly what happened in this case.2011-04-22
  • 0
    @Qiaochu: In one of the threads linked to, you answered the question "Can I ask questions that serve as puzzles? I.e. I already know the answers but post the questions anyway to see if other people can solve the puzzles?" with "You can do whatever you want (within reason), but there are plenty of users whose first instinct will be to Google the puzzle and post a link to a solution online. If you are going to do this, please clarify that you do not want people to just post links to solutions." That doesn't seem to fit with closing this question as off-topic.2011-04-22
  • 0
    @joriki: JFYI I cast my vote after Jonas posted his comment.2011-04-22
  • 1
    @joriki: fine. I have reopened the question, but just so we're clear, my opinion now is different from my opinion when I answered that question and I will edit to reflect that.2011-04-22
  • 0
    @All : Well, I'm sorry for the upset I've caused. I simply found that this was a particularly interesting use of the axiom of choice, and wanted to share it. @Myself : Thanks for the link! To be honest, I've heard this enigma from a friend, with a different context (the dwarves were not prisonners), but I translated it to the general usual framework (prisonners, etc...)2011-04-23

2 Answers 2

12

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.

  • 0
    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.2011-04-22
  • 0
    I didn't say it was countable. Are you saying the dwarves have only countable memory and hence can't remember uncountably many representatives?2011-04-22
  • 0
    @joriki: As Eric had pointed out (in comments to my now deleted answer), I missed the "whisper in my ear" part (hence the difference in our answers). And +1 :-)2011-04-22
  • 0
    @Joriki: Ok sorry, I misunderstood your answer. But indeed the dwarves would require an uncountable amount of memory and worst of all, they would need _uncountable_ choice, right? That seems hard, but maybe I am just underestimating those dwarves because they are small :-)2011-04-22
  • 1
    @Moron: I think the answer you deleted was quite interesting, even though it is in fact an answer to a slightly different question.2011-04-22
  • 1
    @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 :-)2011-04-22
  • 0
    @Myself/joriki: Ok, I have undeleted that answer.2011-04-22
  • 1
    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.2011-04-23
  • 0
    @Alex: There's no *finite* algorithm. But since the dwarves are performing uncountably many steps anyway (you don't seem to be objecting to that), they can compare each sequence to the representatives already chosen and add it if its class isn't represented yet. The number of comparisons to be made has the same cardinality as the number of sequences. Of course they need a very well-ordered brain to schedule an uncountable number of steps -- a mere mortal wouldn't know where to start :-)2011-04-23
  • 0
    @Alex: I guess you could argue that uncountably many operations could be performed in parallel (after all, if the dwarves have uncountable memory, why not have uncountable parallel processing power). But having uncountable parallel processing power and being able to perform uncountably many steps in finite time seem roughly equally implausible to me, so if you're willing to accept at all, quite apart from the axiom of choice, that they have uncountable processing power, then you might as well accept the sequential version of this implausibility, which obviates the need for a finite algorithm.2011-04-23
  • 1
    @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.2011-04-23
3

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.

  • 0
    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?2011-04-22
  • 0
    @joriki: Yes, with parity, no more than one stays imprisoned.2011-04-22
  • 0
    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.2011-04-22
  • 0
    @Eric: Thanks for pointing that out. I missed the "whisper in my ear" part.2011-04-22
  • 0
    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.2011-04-22
  • 0
    @joriki: Are you defining connectivity in terms of finite paths? What you say might well be true, it is just a different way of looking at it, I suppose.2011-04-22
  • 0
    @Moron: I don't think I understand how one could define connectivity in graphs other than in terms of finite paths. An infinite tree can have levels corresponding to higher ordinals that are "reachable" through infinite paths, but for a graph I see no concept of reachability other than finite reachability. In any case, if there is such a thing, it can't restrict the colours of the graph; the set of 2-colourings is necessarily in bijection with the power set of the set of (finitely) connected components.2011-04-22
  • 0
    @joriki: I agree with you (hence I changed the wording of my answer). I am guessing that defining connectivity in terms of non-finite paths is possible too.2011-04-22
  • 0
    Do you have a reference on the web for the Erdos theorem? I knew the lose only a finite number, but not the lose only one. Is this related to the Von Neumann normal form of ordinals, which have only one finite part, so you can define odd/even by that?2011-04-23
  • 0
    @Ross: I have edited the answer with a link. I don't know the details of the proof, but the wiki does mention something.2011-04-23