There is an ancient kingdom where every married women keeps information regarding the fidelity of other men. However what they don't know is the fidelity of their own husbands. Also there is an ancient belief due to which they don't tell each other about the fidelity of their husbands.
On a certain day, the queen of the kingdom declares that she has identified at least one unfaithful man in the kingdom. She allows the wives to identify and gives them authority to kill their husband if they are unfaithful at midnight.
How will the wives manage it?
Let us begin with the assumption that only one man is unfaithful. In that case everyone except wife of his will know about him. But his wife will know that all other men are unfaithful and on the statement of queen that there is at least one unfaithful man in the kingdom, she will shoot his husband at midnight.
Now assume that there are two unfaithful men in the kingdom. Then their wives will know about one unfaithful man. So they will wait for the midnight. But when nobody will be shot at midnight, they will come to know that there must be more than one unfaithful husband and they will come to know that their husband is also unfaithful. Thus both of them will shoot their husbands at midnight.
Assume that there are three unfaithful husbands. Their wives will know about the two unfaithful men and they will wait for two midnights but when nobody will be shot, they will come to know that there are more than two unfaithful men and they will understand that their own husband is unfaithful. Thus they will shoot their husbands at the third midnight.
Thus for any general case where there are n unfaithful husbands, each of their wives will believe there are n-1 unfaithful husband and will be expecting a shot on the midnight of n-1 day. When they don't hear any gunshot, they will realize that their own husband was the nth.
