Cheating Husbands
Mamajorca was a small, tight knit city, in fact small enough to hear a single gunshot from the opposite end of town. Every married woman in the city was a perfect reasoner, having passed an extremely rigorous set of pre-marital academic tests. However, some of the men were not as smart, and they began cheating on their wives. Of course in such a small city, gossip about the cheating husbands quickly spread amongst all the married women. Each of them knew if one of the other wives was being cheated on, though none of the wives were able to discern whether or not their own husbands were being unfaithful.
The great queen of the city, Henrietta I, who was always truthful and to whom all the women were always obedient, decided to put an end to the problem of the cheating husbands in her city. One day, she gathered all of the wives to the town square and announced to them that there was at least one or more cheating husbands in the city. From that time forward, if a wife discovered that her own husband was cheating, she was bound by law to shoot him at midnight of that same day. Despite all of the wives knowing about all of the other cheating husbands, they were all forbidden to speak a word of their knowledge lest the unfaithful men catch wind of the plan and escape their punishment.
Given that there are n (where n > 0) cheating husbands in the city, how many nights will it be before they are all killed?
So, this is a paraphrase of part of the paper I read for my distributed systems course today. It is about determining when information is common knowledge amongst a set of nodes. At least computer scientists know how to make theory somewhat entertaining.
And the answer is on the nth day. The proof is left up to the reader.