Cap Puzzle (Infinite version)
Source: Tanya Khovanova’s Math Blog
Problem: The king has a countable number of wise men. The line starts from the left and is infinite in the right direction. The wise men are all facing to the right and they see the infinite tail of the line. Again, the king places either a black or white hat on each head and they can only say one of two words: black or white. Will they be able to devise a strategy beforehand that ensures that not more than one person makes a mistake?
Reference: This is a followup to the following problem http://pratikpoddarcse.blogspot.com/2009/08/cap-puzzle.html
Update(24/01/10): Solution: Posted by me in comments (taken from a recent blog entry by Saurabh Joshi, IIT Kanpur)
Problem: The king has a countable number of wise men. The line starts from the left and is infinite in the right direction. The wise men are all facing to the right and they see the infinite tail of the line. Again, the king places either a black or white hat on each head and they can only say one of two words: black or white. Will they be able to devise a strategy beforehand that ensures that not more than one person makes a mistake?
Reference: This is a followup to the following problem http://pratikpoddarcse.blogspot.com/2009/08/cap-puzzle.html
Update(24/01/10): Solution: Posted by me in comments (taken from a recent blog entry by Saurabh Joshi, IIT Kanpur)
Solution taken from Saurabh Joshi's blog. He posted the problem long after I did. :P Solution also available on Tanya's blog.
ReplyDeleteIt is based on “Axiom of Choice”.
Let us say two infinite strings s1 and s2 are related, if they are finite hamming distance away from each other. Such a relation is equivalence relation, hence partitions the set of all strings into equivalence classes.
Let these classes be c1,c2, .. ck. So basically, any two strings drawn from a class ci will be finite hamming distance away from each other. For each such class ci, people will fix some representative string si belonging to ci.
Now, a person p looks at given infinite string pi. Lets say that the actual assignment might be given by string S. A person may put 0 or 1 as a guess for his own hat and still both the resulting strings will be in the same class as S and pi. So, having observed a string pi, a person identifies the class ci in which pi belongs, and picks up corresponding representative string si. He announce the color of his/her hat as given by si. Because, si is only finite hamming distance away from S, only finitely many people will guess it wrong.
:)
I admit that its very difficult. :) Took me a while to appreciate the solution.
such a solution seems very shady. even in the spirit of the problem, assuming the axiom of choice, i have very fundamental doubts.
ReplyDeletefirstly, the axiom of choice only says such a function exists, and it does not give a construction of a function or a method to find the function.
secondly, it is a trivial task to show that there are infinite classes (not really c1...ck) with infinite elements each...so this choice function, if found, cannot really be described, accurately, to all the people in finite time...
even if u assume that it can be conveyed to them in a form like "take the min." or something like that, the function is from a set X to a representative element. And by looking at finite number of elements, you cannot classify an element's set. So you have to somehow be able to consider all the infinite elements (each guy standing in the line needs to decide which set, by looking at the rest of the tail), which is not a possible task (im not saying its impractical, but its impossible, because at any time if he decides he has seen enough to decide the set, the rest of the unseen tail might be completely diff and change the class)...
in short, nah, not convinced at all.
I expected that comment from you. You are too late actually. :P
ReplyDeleteAll your accusations are valid. But they are inherent assumptions in the question. You say explaining infinite information to infinite people is not possible. I say yes thats true. But is it possible to see infinite people, Store those infinite values in your memory, Collect information from infinite people and then decide whom to kill, whom not to kill. The whole problem from its first statement is based on the assumption that infinity is within our reach.
Still interested? Read this article.
arey padh liya - and even more interestingly, the comment on that sends you to a 3 year old discussion on this problem at cornellmath.wordpress which has 87 comments, each with all sorts of views on the problem (ppl like terrence tao commented :P)...
ReplyDeletei havent read it all, but yeah, i think if tons of mathematicians itself doubt the solution, its not obvious as to what is implicit and what is not.
the very first problem is to find the choice function knowing it exists :P the second problem is being able to relate an infinite tail to its set (out of infinite sets) and then of course use the infinitely large function to determine the element it should match to.
abhi dekha problem to obv abhi comment aayega :P
even the set of real numbers has this problem of infinity. because the set of real numbers is uncountable. whereas the set of real numbers that we can describe using a language having countable alphabets is countable.
ReplyDeleteTherefore almost all real numbers, with a probabillity 1 in a sense,are not accessible to us. Yet we beliieve in their existence and use it merrily in real analysis and calculus.
a nice article on internet is here
the axiom of choice can be avoided if we assume additional restriction that the caps are placed based on an undisclosed algorithm.
ReplyDeletebasic idea is that all algorithms for generating sequence of 0 and 1 can be considered as a turing machine which can be encoded as a finite string of 0 and 1. Therefore each such infinite sequence can be mapped to a set of {0,1} strings, corresponding to algorithms that generate the sequence.
Strategy:
step 1 : First decide on any encoding method of turing machines i.e. algorithms.
Step 2 : Consider each sequence of caps as a sequence of 0 and 1 treating black as 0 and white as 1. After caps have been placed,each man can see all except a finite number of caps. let S be set of all {0,1} strings which, considered as an algorithm, generate a sequence at a finite hamming distance away from real sequence.
step 3: Lexicographically order S. let f(S) be smallest member of S. Everyone will answer his cap's color based on algorithm corresponding to string f(S).
solution posted by pratik above ensures that only a finite no. of people get it wrong. however, with small alteration u can ensure that not more than one person gets it wrong.
ReplyDeletethe first person will just signal the number of places at which the representative string differs from the string he sees. based on answer of first person,second person can deduce his hat color. now the third person can deduce his color and so on. Except possibly for the first person, everyone will guess correctly.