Posts Tagged ‘axiom of choice’

Puzzle : Black and White hats!

January 3, 2011

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

Advertisements

Puzzle : Black and White Hats Revisited

January 23, 2010

Well,
I have been very lazy and irregular these days so I am not even trying to commit that I will be so in future :-). Here are two very nice puzzles, thanks to Ramprasad.

Problem : A person is standing on each natural number belonging to N. Yes, that means that there are countably infinite people standing in a straight line 1,2 …..infinity. As always, black or white hats are placed on each of them. This gives rise to a random string of infinite length. A person can see everybody else’s hat but not his/her own. Everybody has to guess the color of their hat simultaneous. No communication between any two people is allowed.

1) Come up with a strategy so that infinitely many people guesses the color of their hat correctly.

2) Come up with a strategy so that only finitely many people guesses the color of their hat incorrectly.

Solution :

Well, 1st puzzle is comparatively easy to solve. I will give two solutions, here
1a ) This solution is by deepanjan. A person standing on position p, looks towards infinity and see if he/she sees any black hat. If he/she sees a black hat, the person will announce that his/her hat is black. Otherwise announce that his/her hat is white.

Why would it work?
Let us say, there are only finitely many black hats placed. In such a case, there must be a largest position bp such that for all position greater than bp, hats are white. In such a case, all people standing on position greater than bp will look towards infinity and will see no black hats so they will announce their hat as white. Hence, infinitely many people guessed the color of their hat correctly.

What if black hat appears infinitely often? In that case, any person with a black hat, would be able to see another black hat when he/she looks towards infinity. Hence, all persons wearing a black hat will guess it right. Again, they are infinitely many of them.

1b) A person on position 2p-1 will pair up with person standing at position 2p. Let us call them p1 and p2. p1 will guess the color of his/her hat to be the same as p2. p2 on the other hand will guess the color of his/her hat to be different than p1. Obviously, one of them has to be right. Meaning, half of the people will guess it right.

2) Solution for two is tricky. It 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. 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.

Phew, did not know that innocuous looking “Axiom of Choice” could be so powerful mathematical tool.