Common knowledge

In this post, I want to talk about some puzzles which deal with common knowledge, or rather a change in the common knowledge. In logic, something is a common knowledge if it is known to all, if they know that they all know it, if they know that they know… so on ad infinitum.

The first one involves cheating husbands. In a village it so happens that  some all the husbands cheat on their wives but the more interesting part is that everyone knows about the cheaters but for the poor wives. The wife of a cheater knows all the cheaters in the village except her husband because if she knew she would surely kill him (No compromises). So they don’t talk to each other about  this cheating business. One day a fakir who always speaks the truth  (as opposed to the truth , the whole truth and nothing but the truth) comes to the village and tells the villagers that there is at least one cheater in the village. What effect if any do the fakir‘s words have on the lives of the villagers?1

An identical problem that had been circulating on the web a while ago concerned a group of 1000 islanders who either had blue eyes or brown eyes. They know the eye colour of every other person but theirs and their religion forbids them from conversing about their eye colours. This was because once they know their eye colour they have to sacrifice themselves to the God (and they are so loyal that they do). Once a foreigner comes to the island and oblivious to these rules exclaimed that he was happy to see at least one other blue eyed person on the island. For the sake of answering the question, we can assume that there are 250 people with blue eyes. Again would the foreigner’s statement in any way affect the islanders?

As always the hard problem (at least it was for me) comes last. A questioner  hands out an envelope each to two people with a number written on them. The  questioner tells them that the two numbers are consecutive (n and n+1). Each person knows the number on his envelope but not on the other person’s. Then he asks them one after  another whether they know what the two numbers are to which they are to reply  either “I know” or “I don’t know” and nothing else. It turns out that after a few such rounds of saying “I don’t know”, one of them suddenly says “I know” following the other person immediately says “Now, I know too”  (Don’t nitpick. The game is over.) What was the logic if any that was used by the two people to come up with the numbers? There was no planning before, no cheating and the two people are eminent logicians.

SPOILER ALERT! Answers in the next paragraph.

In all of the above cases, it so happens the new information radically changes the common knowledge of the group and leads to the death of all the cheating husbands in the first problem and the suicide of all the islanders in 1000 days in the second problem. In the last puzzle, no matter how big the two consecutive numbers are they always get the two numbers in the end if questioned enough number of times.


1.Thanks Anant (LK) for clearing up “some” issues. If all the husbands are not cheaters, then there is a good chance that innocent husbands would get killed.

Advertisements

5 comments

  1. I've seen a proof by induction for the solution of the islander problem. I didn't, also couldn't, work through the proof. It gets painfully convoluted after three layers of 'they know that they know that they know'…

  2. These problems are always easy to interpret if the steps are separated with each question not depending on the previous. For example, the last problem boils down to this- Each person asks the other of the nth digit of their number in binary is equal to 0 or 1 (for their nth turn). True, there is no preplanned method to ask questions but assuming the binary notation is as good as knowing that the other person will tell yes or no to each question he asks.

  3. @ Kroor and it's kroor. 🙂 You need not work out all the way till the end. That is the whole point of a proof by induction. And you were the one who first asked me this problem.@ Anant. Your solution is brilliant. Mine was more like a reductio ad absurdum chopping of impossible numbers after each round of questioning.

  4. For 1000 islander’s problem:
    Lets do backward induction.
    1) when we have one blue eye color islander alive, that statement will make him commit suicide. Ob!
    2) what will happen when we have 2 blue eye color islanders? (I am assuming that at any point they do not know the exact number of blue eye color junta.) If i see at least one blue existing, i still have prob that i will not have blue eyes. (or in common knowledge way: i know that there is non-zero prob that others know that i don’t have blue eyes)

  5. When there are two islanders, no one dies the first day as both the blue-eyed persons see each other (and expects him to die that day). But nobody dies that day and they see only one blue-eyed person. Hence they both reach the obvious conclusion that they both must have blue eyes themselves and die the next day.

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