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.

Advertisements

Tags: , , ,

4 Responses to “Puzzle : Black and White Hats Revisited”

  1. Pratik Poddar Says:

    Thanx a ton. I was not able to solve the second part since a long time. Interesting solution. Thanx.

    Pratik Poddar

  2. Puzzle : Black and white hats revisited, .. yet again! « Me, Myself and Mathematics Says:

    […] Saurabh Joshi’s Blog about math, algorithms, theorems, puzzles …. « Puzzle : Black and White Hats Revisited Puzzle : Secret Sharing […]

  3. Puzzle : Coloured Hats and Wizards! « Me, Myself and Mathematics Says:

    […] post : here, here and […]

  4. Puzzle : Black and White hats! « Me, Myself and Mathematics Says:

    […] : 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 […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: