The puzzle of unfaithful wives is usually stated as follows:
There was a country in which one million married couples inhabited. Among these one million wives, 40 wives were unfaithful. The situation was that each husband knew whether other men's wives were unfaithful but he did now know whether his wife was unfaithful. One day (call it the first day). the King of the country publicized the following decree:
(i) There is at least one unfaithful wife.
(ii) Each husband knows whether other men's wives are unfaithful or not.
(iii) Every night (from tonight) each man must do his deduction, based on his knowledge so far, and try to prove whether his wife is unfaithful or not.
(iv) Each man, who has succeeded in proving that his wife is unfaithful, must chop off his wife's head next morning.
(v) Every morning each man must see whether somebody chops off his wife's head.
(vi) Each man's knowledge before this decree is publicized consists only of the knowledge about other men's wive's unfaithfulness.
The problem is ``what will happen under this situation?" The answer is that on the 41st day 40 unfaithful wives will have their heads chopped off. We will treat this puzzle in a formal manner.