Hi,
This very nice puzzle was brought to me by Ramprasad.
Problem : Set of people ( infinite ) are standing on a line of natural numbers. That is they are standing at position 1, 2, 3 …. and so on. White or black hats are put randomly on all of them. What strategy can they decide on so that either all of them guess the color of their hat right, or none of them get it right?
Solution : I hope you guyz remember another puzzle on the similar lines. In fact, you better read that post and I am going to refer to the strategy employed there. Remember that in that earlier puzzle, they have to come up with a strategy so that only finitely many of them guesses it wrong. So we partitioned set of all strings into groups such that strings belonging to one group are only finite hamming distance away from each other. And then using axiom of choice we have a representative strings C1,C2…. in each group.
Now, the hint is, suppose you are one of the people standing. What additional information do you need to know whether you guessed it right or wrong? Think about it.
Well, if someone tells you the hamming distance of the string S ( in which you belong ) and the representative string Ci, then you know whether you guessed it right or wrong. Because, if you see that S’ ( all but you ) differs from the representative string by distance d, then you have guessed your color right. If you see the difference at d-1 position, then you know that you are in one of the position where two strings differ so you must have guessed it wrong.
There you go! That is the hint. All of them decide on to guess that the string S differs only at d locations where d is odd. Now, if S differs at locations d’ where d’ is even. All those people at position which does not differ from representative string Ci, they will see the difference of d’. But as decided, they will try to make the distance odd, so they will choose the opposite color as given by the representative string. Hence, all of them will guess it wrong. For a person who is in a position which differs from Ci, he will see the difference of d’-1 ( which is odd ) so he will go with the color mentioned in the representative string and thus guesses it wrong.
it is easy to see that if the distance of S is indeed odd, all of them will get it right.
Cool trick, isn’t it? Well, the solution I thought it by myself, with the hint given by Ramprasad.
Related posts : here, here, here and here
— Saurabh Joshi
Me, Myself and Mathematics 