20
$\begingroup$

I have heard of the puzzle with 100 or 10 dwarves wearing a hat of a color, either red or blue, and standing in a straight line, and having to guess the color of their own hat - it's quite easy.

The solution to save all dwarves or all dwarves minus the first one is fairly simple and relies on the fact that the number of dwarves is finite. So what would happen if you had an infinite number of dwarves standing in a straight line?

Every dwarf wears a hat of color either red or blue and sees the color of the hats of all the dwarves standing in front of him. There is explicitly a first dwarf, who has to start guessing the color of his hat and then the guessing proceeds with the next one in the line.

If a dwarf guessed correctly, it is freed; if he guessed wrong, it is fried. Every dwarf can hear the voice of all other dwarves without a problem. Everybody is only allowed to speak out either the color red or blue, but no further information.

Is there a possibility for all dwarves to be freed? Well, probably no.

But is it at least possible that only finitely many of them are killed?

EDIT: This is a mathematical puzzle. No loopholes.

$\endgroup$
  • 2
    $\begingroup$ I think you should specify that the dwafs are facing the "infinite" direction. More specifically, that the dwarfs can be labeled by natural numbers, where each dwarf sees the dwarfs greater than it. $\endgroup$ – xnor Jan 12 '15 at 9:07
  • $\begingroup$ Are they allowed to discuss any kind of strategy before they go into this situation? $\endgroup$ – EFrog Jan 12 '15 at 9:16
  • 1
    $\begingroup$ Is this what you are searching for? $\endgroup$ – dmg Jan 12 '15 at 9:17
  • $\begingroup$ @dmg I don't understand that at all. There is an infinite number of possible sequences of hats a dwarf can see in front of him, so making a label for each sequence would be impossible. Especially if the only labels you can offer are "red" and "blue". I.e, just because the guy behind me says blue can't possibly determine whether my hat is red or blue, no matter what I see in front of me. Is there a way I can see examples of this in action? $\endgroup$ – EFrog Jan 12 '15 at 9:27
  • 1
    $\begingroup$ I'm a little lost. What happens if every dwarf is wearing the same color hat? Or the colors are in a ratio of 7:3? Do there need to be an even number of blue and red hats? $\endgroup$ – SocioMatt Jan 12 '15 at 14:43
7
$\begingroup$

This puzzle has been discussed on the Mathematics Stack Exchange as in this question: Prisoners Problem.

The solution given there (by Asaf Karagila):

Encode the colors into $0$ and $1$, and define the equivalence relation on $2^\Bbb N$, $\langle x_i\rangle\sim\langle y_i\rangle$ if and only if there is some $k$ such that for all $n\geq k$, $x_n=y_n$. Using the axiom of choice the prisoners pick a representative from each equivalence class.

In his turn, the $n$-th prisoner looks for the representative class fitting the string of hats he sees ahead, assuming that all hats up to him are blue. Since all the prisoners follow the same representative to guess their own color, it is guaranteed that after finitely many deaths, the representative and the fashionable selection of hats by the warden will agree, and everyone else will survive.

Note that since the Axiom of Choice is non-constructive, so is this solution and hence may not be practically useful for the dwarves in the question. There seems to be a fair bit of discussion on whether the Axiom of Choice is required. Well it was shown by Hardin and Taylor [Hardin, Christopher S.; Taylor, Alan D. An introduction to infinite hat problems. Math. Intelligencer 30 (2008), no. 4, 20–25] that there being no winning strategy is consistent with ZF (plus other axioms which don't imply the Axiom of Choice). So in that sense the Axiom of Choice is necessary for a winning strategy.

$\endgroup$
7
$\begingroup$

The solution is the following:

We define the notion of a class of infinite sequence of hats. All sequences in this class differ from each other by only a finite number of elements. There are an infinite number of classes, each containing a infinite number of elements.

Why? As differences between classes are of infinite length, there is an infinite number of possible distances, which means there is an infinite number of classes.

For each such class we select a "representative" which is a single element of the class (a single infinite sequence of hats). So suppose we have the class "infinitely alternating red and blue, with a finite number of non-alternating hats in the first 20 elements". We can set the representative to be:

EDIT: Apparently, after digging a bit, a good way to define the classes is:

Two sequences are equivalent if they are identical after a finite number of items

Choice of a representative can be easily defined as choosing the sequence where the differences appear at the beginning of the sequence and are lexicographically smaller.

For example, the sequence

rbrbrbrbrbrb...

And, the sequence:

r[r]rb[br]rbrbrb... ([] denotes mismatches)

is a member of that class. Each dwarf can see the infinite sequence of hats in front of it and can recognize the class. The dwarves can see the mismatches in front of them, but do not know if their own hat is not a mismatch.

But, the difference is finite, and a modification of the standard rules for guessing a finite sequence can be applied. The first dwarf says "red" if there is an odd number of hats that are different in the "sequence", compared to the "representative" (or "blue" if the mismatches are even). From there on, each dwarf has sufficient info to tell the colour of their hat.

Note that, the number of classes is infinite, however, since we are talking about infinite dwarves, I assume this is acceptable.

Finally, since the first dwarf "guesses", the first dwarf has a 50% chance of survival, all other dwarves survive.

Oh, and because of the infinite number of classes, this can be directly applied to the problem with an infinite number of colours.

Summary for the naysayers

  • Two sequences are equivalent if they are identical after a finite number of items.

  • Choice of a representative can be easily defined as choosing the sequence where the differences appear at the beginning of the sequence and are lexicographically smaller.

  • As the sequence is infinite, and differences are finite, there exists an infinite subsequence, that can uniquely define the class of the sequence.

$\endgroup$
  • $\begingroup$ There is discussion at: chat.stackexchange.com/rooms/20187/… $\endgroup$ – Steve Jessop Jan 12 '15 at 16:25
  • 1
    $\begingroup$ Whoops, sorry, I tried to move the comments to chat, purged all the comments, and then realized I couldn't undelete my comment with the chatroom link on mobile. My bad; thanks for finding it. $\endgroup$ – Doorknob Jan 12 '15 at 16:31
  • 7
    $\begingroup$ I think you should mention that the axiom of choice is being used to pick the representative elements. You can't choose the lexicographically smallest element of the class, as there may be no minimum like for rrrrrr... . There is no constructive algorithm to find representatives. $\endgroup$ – xnor Jan 12 '15 at 19:07
  • $\begingroup$ How do we choose the class? It is because each dwarf is preceded by a finite number of dwarfs, and therefore can always see the class after him? $\endgroup$ – njzk2 Jan 12 '15 at 19:38
  • 5
    $\begingroup$ Anyway, this answer is a bit like solving a puzzle "I have one ball and a knife. I need two balls. How do I get them?" by appealing to the Banach-Tarski dissection. Perfectly reasonable as long as the puzzle is about surprising consequences of the axiom of choice, not about actual balls cut up with actual knives. The answer makes a point, but the point is not about what dwarfs in hats can do, it's about uncountable infinities. $\endgroup$ – Steve Jessop Jan 13 '15 at 13:53
2
$\begingroup$

Refer to the following link. The one answer which is simple to understand is the High pitch and low pitch. Each dwarfs answers his hat color in either high pitch or low pitch depending on the next dwarfs hat whether its in Red or Blue color.

$\endgroup$
  • $\begingroup$ Well that's certainly got the merit of simplicity! $\endgroup$ – A E Jan 12 '15 at 13:42
  • 1
    $\begingroup$ The linked question is explicitly about the finite case; and your answer, while clever, isn't really satisfying: the intent is clearly that each dwarf can communicate only one bit to the neighbor in front of him. $\endgroup$ – Daniel Wagner Jan 12 '15 at 14:30
  • 3
    $\begingroup$ They could impart several bits, if required: high/low, loud/quiet, fast/slow - and remember that humans (and presumably dwarves) are not binary - we can at the very least differentiate three (high/normal/low, fast/normal/slow, loud/normal/quiet) levels for each of these measurements. I make that a minimum of 27 bits even assuming that three levels per measurement is as as fine grained as we can get, that there is only one word and there are no other ways to inflect the word. $\endgroup$ – Jon Story Jan 12 '15 at 17:11
  • $\begingroup$ No, this is wrong. The dwarves can only call out a hat color, they can't do it in different pitches. $\endgroup$ – Gilles Jan 12 '15 at 17:14
  • 8
    $\begingroup$ Says who? I don't see that in the rules $\endgroup$ – Jon Story Jan 12 '15 at 17:15
-1
$\begingroup$

I was wondering if a dwarf with infinite range of sight can identify repeating pattern(s)?

What if there is only one single pattern that is infinite? This would mean the dwarfs can't be saved :(

Due to the fact that the number of dwarfs is infinite, there must be a repeating pattern at some point (this is almost too complicated for me now!). With infinite sight, every dwarf can find his own position within the repeating pattern (which can be very, very, very long).

Having said that, a dwarf can never be sure whether he really identified a pattern correctly since the number of dwarfs is infinite and he would have to see all dwarfs at once in order to be sure - which is impossible due to "infinite number",... I think?

$\endgroup$
  • 1
    $\begingroup$ There can be an infinite sequence which does not have a repeating pattern. For example rbrrbbrrrbbb... $\endgroup$ – dmg Jan 13 '15 at 7:53
  • $\begingroup$ @dmg (read the <strike>'deleted'</strike> line). You are right, but it is infinite and 'infinite' includes the guarantee of a repeating pattern somewhere. I think this is a matter of definition? $\endgroup$ – Avigrail Jan 13 '15 at 8:12
  • 1
    $\begingroup$ PI is an example of a non-repeating infinite pattern. $\endgroup$ – dmg Jan 13 '15 at 8:29
  • 2
    $\begingroup$ The brain doesn't really handle infinity well :) Just look at Cantor $\endgroup$ – dmg Jan 13 '15 at 8:40
  • 1
    $\begingroup$ @bobbee: ah, yes, watching the best monkey out of an infinite number of monkeys play chess is awesome. I was referring to watching one monkey play chess ;-) $\endgroup$ – Steve Jessop Jan 13 '15 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.