This question already has an answer here:
- Unfaithful husbands [duplicate] 1 answer
I found this cool problem in Santos' number theory book, page 12, but he gives the credit to Halmos.Supposedly it must be solved by mathematical induction.
Every man in a village knows instantly when another’s wife is unfaithful, but never when his own is. Each man is completely intelligent and knows that every other man is. The law of the village demands that when a man can PROVE that his wife has been unfaithful, he must shoot her before sundown the same day. Every man is completely law-abiding. One day the mayor announces that there is at least one unfaithful wife in the village. The mayor always tells the truth, and every man believes him. If in fact there are exactly forty unfaithful wives in the village (but that fact is not known to the men,) what will happen after the mayor’s announcement?
I defined $P(n)$ to be the number of unfaithful wives in the village. Then since everyone believes the mayor and he always tells the truth, $P(1)$ must be true. This is why I defined $P(n)$ to be the number of unfaithful wives in the village, because we've been told that $P(1)$ is true. Now I have to prove that if $P(k)$ is true, i.e. $k$ women are unfaithful, then $P(k+1)$ is true. I guess this must be somehow related to men knowing the unfaithful women in the village, but I can't proceed. I have made some different guesses in my mind, but I can't logically entail anything out of them yet.
Any hints or ideas will be appreciated.