Puzzle : Black and White Hats Revisited

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.

Tags: axiom of choice, black and white hats, math, puzzles