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 this question: Knowing that at least 98 husbands have cheated (the queen doesn't know about the king's infidelity and the women all assume the innocence of their own husbands), why would the queen announce this unless she wanted all of them to die? Would it be better for the village to kill off so many men or for the women never to tell each other about what their husbands have been doing?
In the end, they come to the conclusion that the only woman that deserves to be alone for the rest of her life is their evil queen. But if they all go and tell her who her husband, the king, has been sleeping with, she will see that they will not tell each other the truth and have instead plotted against her. And after killing the king, in retaliation, there is a strong possibility she may tell them all that their husbands have cheated.
To save their village, they decide not to tell each other and not tell the queen about the king. Instead they tell their husbands what evil plans the queen had in mind for the village. Then angered, knowing their queen is dangerous and unfit to rule, the whole village gets together and kills her. The king, knowing the entire village has just saved his life, doesn’t try to stop them and is forever grateful to the women of the village.
Do you agree with my answer?