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.
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.