A Queen of an island kingdom was concerned about the high level of infidelity among the island's men, so she gathered all the married women of the island and made the following announcement:
"There is at least one unfaithful husband in our kingdom. All the wives know of all the unfaithful husbands, but know nothing about their own husband. You are not allowed to discuss your husband with any of the other women, but if it becomes known to you that your man is unfaithful, you must shoot him at midnight of the following night."
(Assume a shot anywhere on the island is heard at any other point on the island.)
After thirty nine nights of uneasy quiet, on the fortieth night the gunshots echoed across the island. How many men were shot that night, and why? (Assume the wives are all super smart.)
If every wife on the island knows about all the other women's husbands, but not her own, she will either:
Know about all the cheating husbands, if her husband is faithful
Know all but one of the cheaters, if her husband cheated on her.
Thus if there is one cheating husband, his wife will know about no other cheaters. But since the queen said that there is at least one exists, she will realise that the cheater is her husband, and kill him in the first night.
If there are two cheaters, their wives will only know of one cheater each. They will also know that if the one cheater they know about is the only cheater on the island, he will be killed the first night. (See above.) Since they do not hear a shot the first night, they will realize that there are more than one cheaters on the island, and the second one is their husband. So they will shoot their husbands on the second day.
In general, if there are N cheaters, their N wives will know of N-1 husbands, and expect these people to be shot on the N-1'st night. When no shooting happens, they realise that there are actually one more cheaters than they know about, and that their husband is the extra one. The N are then shot on the Nth night.
Thus, if the shots were fired on the 40th night, that means that 40 of the husbands were unfaithful.
|
|
Posted by assaf
on 2007-01-13 11:12:10 |
Solution
