Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. Everyone knows that the queen only speaks the truth. What happens?
Let’s assume that there is only 1 cheating husband. Then his wife doesn’t see anybody cheating, so she knows he cheats, and she will kill him that very day.
Now, let’s say that there are 2 cheating husbands. There will be 98 women in the town who know who the 2 cheaters are. The 2 wives, who are being cheated on, would think that there is only 1 cheater in the town. Since neither of these 2 women know that their husbands are cheaters, they both do not report their husbands in on the day of the announcement. The next day, when the 2 women see that no husband was executed, they realize that there could only be one explanation – both their husbands are cheaters. Thus, on the second day, 2 husbands are executed.
Through mathematical induction, it can be proved that when this logic is applied to n cheating husbands, they all die on the n th day after the queen’s announcement. So with 100 cheating husbands, all of them will be executed on the 100th day.