# A problem due to Halmos in Santos' number theory [duplicate]

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.

## marked as duplicate by Omnomnomnom, Shuhao Cao, Dan Rust, Vedran Šego, Git GudAug 27 '13 at 1:05

• Are you sure that the $P(n)$ you defined is useful for the problem? What are you trying to prove (:? Perhaps it would be more useful to have $P(n)$ represent what might happen upon knowing that there are $n$ unfaithful wives. So, for $P(1)$, the statement might be: $X$ happens when there is 1 unfaithful wife, for some statement $X$. Fill in $X$! – Raymond Cheng Aug 26 '13 at 16:05
• the same puzzle is also seen here with a more thorough discussion – Omnomnomnom Aug 27 '13 at 0:27
• See also here. – Andrés E. Caicedo Jan 15 '14 at 7:15

Suppose that there is only one unfaithful wife. Then all men except for her husband perceive the wife to be unfaithful. However, he knows by the mayor's announcement that there is at least one unfaithful wife. Since he is unable to otherwise account for the unfaithful wife, he deduces that the unfaithful wife must be his own.

Having deduced that his wife is unfaithful, he shoots her before sundown the same day.

Now, suppose that there are $2$ unfaithful wives. All men except for the two husbands perceive two wives to be unfaithful. The two husbands, however, perceive only one unfaithful wife. Following the above logic, they know that if there is exactly one unfaithful wife...

Perceiving no deaths by the end of the first day, both men may now deduce that their wives are unfaithful, and shoot them by sundown the second day.

The pattern continues.

A "more mathematically rigorous" phrasing, as requested:

Let $P(n)$ be the statement: "if $n$ wives are unfaithful, then all $n$ wives will be shot before sunset on the $n^{th}$ day, starting the day of the announcement, with no deaths preceding this day". Our inductive proof is as follows:

By the above argument, we know that $P(1)$ is true. For our inductive step, we must show that $P(k)\implies P(k+1)$. We may do so as follows:

Suppose that there are $k+1$ unfaithful wives (UWs for short). The $k+1$ corresponding husbands (CHs for short) each perceive $k$ UWs, and each deduce that either there are $k$ total UWs or there are $k+1$ UWs total, which means that their wives are unfaithful.

By their perfect knowledge and intelligence, each CH is aware of $P(k)$. On the $(k+1)^{th}$ day, the CHs perceive no deaths, and deduce via $P(k)$ that there cannot be only $k$ total UWs. They thereby deduce that their wives are unfaithful after sundown of the $k^{th}$ day.

$P(k+1)$ follows.

Thus, $P(k)\implies P(k+1)$. Our inductive proof is complete.

If you are still confused about why all wives are not shot, try to trace the reasoning of a man whose wife is faithful. He knows $P(n)$ to be true. When the $n^{th}$ day comes, all $n$ of the unfaithful wives he perceived are shot. Having witnessed this event, he knows that his wife is faithful.

• +1. So, the fact there are exactly 40 unfaithful ones is completely ignored by mathematical induction and all wives will finally be shot, including the innocent faithful ones. Why does this happen? – user66733 Aug 26 '13 at 16:13
• You've gone wrong with your induction somewhere. What is the general pattern? – Omnomnomnom Aug 26 '13 at 16:13
• To be more clear: not all wives will be shot, supposing there are innocent wives. Also, an important aspect of the question is not only if the wives will be shot, but when. – Omnomnomnom Aug 26 '13 at 16:19
• Also, note that the death of any innocent wives supposes that some man broke the law or came to an incorrect conclusion. This contradicts the supposition that each man is law-abiding and completely intelligent. – Omnomnomnom Aug 26 '13 at 17:23
• How does the mayor's announcement make any difference or start a "count-down to death" clock? According to the conditions of the problem, every man knows of 39 unfaithful wives; all but 40 know of 40 unfaithful wives, before the mayor does anything... – DJohnM Aug 26 '13 at 21:57