Sunday 11 September 2016

mathematics - Infinitely many dwarves wearing hats of 2 colours



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.



Answer



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.


No comments:

Post a Comment

Understanding Stagnation point in pitot fluid

What is stagnation point in fluid mechanics. At the open end of the pitot tube the velocity of the fluid becomes zero.But that should result...