A question to ponder

I picked this question out of a list of 140 Google interview questions and thought I'd post it along with my answer. 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. What happens? My answer: The queen is executed. Here is why... Each woman, including the queen knows this truth: If all the men that they know about die, (assuming the innocence of their own husband) there will be at most only one man left in the village. They also know it is possible that all the men in the village will die, leaving no men at all for any of them. Each woman in the village is faced with ...