Question: A certain town comprises of 100 married couples. Everyone in the town lives by the following rule: If a husband cheats on his wife, the husband is executed as soon as his wife finds out about him. All the women in the town only gossip about the husbands of other women. No woman ever tells another woman if her husband is cheating on her. So every woman in the town knows about all the cheating husbands in the town except her own. It can also be assumed that a husband remains silent about his infidelity. One day, the mayor of the town announces to the whole town that there is at least 1 cheating husband in the town. What do you think happens?
Answer: Stumped? Let’s solve this methodically. Say there was only 1 cheating husband in the town. There will be 99 women who know exactly who the cheater is. The 1 remaining woman, who is being cheated on, would have assumed there are no cheaters. But now that the mayor has confirmed that there is at least one cheater, she realizes that her own husband must be cheating on her. So her husband gets executed on the day of the announcement.
Now let’s assume there are 2 cheaters in the town. There will be 98 women in the town who know who the 2 cheaters are. The 2 wives, who are being cheated on, would think that there is only 1 cheater in the town. Since neither of these 2 women know that their husbands are cheaters, they both do not report their husbands in on the day of the announcement. The next day, when the 2 women see that no husband was executed, they realize that there could only be one explanation – both their husbands are cheaters. Thus, on the second day, 2 husbands are executed.
Through induction, it can be proved that when this logic is applied to n cheating husbands, they all die on the n th day after the mayor’s announcement.
Related posts:
I don’t think the induction makes sense here. It only works for cases where a woman thinks there are no cheaters, or where a woman thinks another woman thinks there are no cheaters because the mayor only reveals there is at least one cheater. Once we have 3 or more cheaters it’s not conflicting info to any wife, or any assumed wife’s knowledge so it would not be surprising if no cheater was reported.
Let’s start by assuming we have only 2 couples (not 100).
. Fb however knows she’s done nothing wrong, so the only cheater can be her husband, so she promptly proceeds and kills Mb.
Fa Fb (the ladies)
Ma Mb (the men)
We have 2 possible situations:
1) Fa cheated with Mb, Fb and Ma done nothing. Once the announcement was made, Fa knows the other guy cheated, namely with herself
2) Fa and Fb both cheated with the other guy, so they both know there’s at least the other husband who cheated and wait for the other lady to do the kill. If nothing happens on day, they have to conclude that oups! there was an other cheater in town, namely her own husband as well. So on Day 2 both ladies kill their husbands.
Let’s move now to a situation with 3 couples
Fa Fb Fc
Ma Mb Mc
Here we have 3 possibilities:
1) Ma, Mb are “clean”, Mc cheated with let’s say Fb >> Fa, Fb both know about Mc but have no clue about their own guys. Fc KNOWS that Ma & Mb are clean, so the only left possibility is that her Mc was the cheater so she promptly proceeds to the killing. (this was on day1)
2) Ma clean, Mb, Mc cheated (Mb with Fa, Mc with Fb) >> Fc knows she’s done nothing wrong, and she knows Mb cheated. Knows nothing about Mc though. So she waits that Fb kills Mb. Next day nothing happens, so know Fc realizes Mc must have cheated too, so Fc kills Mc on day 2. Fa knows that Mb & Mc cheated, has no clue about Ma, assumes Ma not guilty, Ma survives. Day 1 brings no relevant clue to her, but once Mc was killed on day 2 she knows Ma was not cheating. As for Fb she only knows that Mc was cheating, so waits for Fc to kill him. Nothing happens on day1, she also knows that Ma did not cheat, on day 2 she realizes Mb must have cheated too, kills the guy.
3) Yup, in this case everyone cheated with everyone (Fa-Mb,Fb-Mc,Fc-Ma). (pheeee, what a village!)
SO Fa knows Mb, Mc cheated, waits for Fb and Mc to kill them. On day 1 nothing happens, as Fb knows about Ma and Mc cheating as well (but not about Mb) and Mc knows Ma & Mb were cheating (no clue about Mc). On day 2, nothing happens, as none can yet be sure about her own husband. On day 3 however, Fa realizes that as long as Mb & Mc did not get killed yet, Ma must have cheated too, so she kills him. Fb and Fc follow the same judgement about their own guys, so all 3 get killed on day 3.
We can now generalize and say that depending on the cheating habits, if there were x guys who cheated the day prior the announcement was made, they will all get killed on day x with the maximum of 100 cheating guys being killed on day 100.
(so for ex. if 20 guys were cheating, they’ll get killed on the 20th day)
(my brains are on fire! help!)
the mayor was a man and a women
Chris is absolutely correct.
If there are n cheaters, each of the cheater’s wife will know that her husband is a cheater on the n’th day. So on n’th day all of the cheaters will be killed.
Thanks,
AngelS
I totaly agree with Lars.
Importtant by other words:
- All not cheated wifes is one set (know same ifnformation).
- But all cheated wife are not other set.
Each cheated wife is separete set, because each knows other information.
@Doetoe, I thought the same as you for a long time… that “If there are n > 1 cheaters, the mayor’s announcement doesn’t seem to add any information.” But it does add something: The information presented by the mayor, although already known by everyone, was not “common knowledge” in the technical sense that everyone knew that everyone knew that everyone knew it (to the 99th degree) there was at least one cheater. Good explanation here: http://en.wikipedia.org/wiki/Common_knowledge_%28logic%29#Example
So, assuming we fix the synchronization problem, this question does work.
This problem is clearly not complete…The blue-eyed islanders problem had a clause which stated that the islanders would leave(or suicide) at a particular point in the day this provided a clear event which the islanders used for the logical deductions.
When there is no time period mentioned as such then the situation is chaotic.
We can only assume that the time taken for a wife to solve the problem-t(n) is proportional(or monotonically increasing) to n the number of cheaters.Then every wife would wait till t(100) and then get their husbands killed.
No Ryn,
The way it works is that each wife know about all the cheaters apart from their own.
If there are 2 cheaters then the wife of a cheater on day one would not know that her husband is a cheater as the one she knows about could be the only cheater.
(for some reason we are saying executions happen at end of day and they find out in the morning who has been killed)
Anyway on day 2 the woman realizes that no one was killed therefore there wasn’t only 1 cheater but 2 therefore her husband is a cheater as well and off he goes to get his head chopped off.
If there were more cheaters then the same process happens but at a later day because remember they know about ALL other cheaters so if they wait 4 days that means there is 4 cheaters and if they only know about 3 then theirs is a cheater.
Hope that made sense
I thought the mayor was women.
Unless the mayor states the exact number of cheating husbands, the only time a wife can deduce her husband is the cheater is when there is ONLY 1 cheating husband. Knowing that there is at least 1 cheater, and since she’s not in the know, clearly lets her deduce that her husband must be the cheater.
If more than 1 husband is cheating, and the mayor still only says “at least 1 is cheating”, all wives will have heard the gossip about at least 1 or more husbands and would have no way of knowing if their husband is in that cheating group. ONLY if they have the exact cheating number can a wife, who only knows about all but 1 of the cheaters, be sure hers is also a cheater.
The puzzle posits no interaction, or synchronization, between the wives other than to gossip about cheaters to all EXCEPT the maligned wife. So, lacking a specific number of cheaters prevents any wife from deducing hers is also a cheater.
Another issue….assuming wives had that exact number and were able to deduce their husband belonged on that list of cheaters, why would it take more than the second day to kill off the cheaters? All wives with cheating husbands would know by the second day that their’s was also cheating and would have reported that fact to the mayor. All executions would, therefore, occur on the second day.
Hmm doesn’t the answer make an assumption that there is something like a synchronization when it says “the next day”?
In the exercise it says “the husband is executed as soon as his wife finds out about him”. With one cheating husband it’s easy: The cheated wife *immediately* knows that she was cheated on and has her husband killed.
But imagine there are 2 cheaters and there is no synchronization between the wifes. Let’s say, we don’t know how long it takes a wife to figure out whether or not she was cheated on.
How could cheated wife #1 know whether:
a) cheated wife #2 decided not to kill her husband because she has doubts OR
b) cheated wife #2 is still thinking?
Did you ever consider that the Mayor could be a woman and of course is part of the population
Suppose that wife A and B are being cheated on, so there are n>1 cheaters. Both wives know that there is at least 1 cheater (the other wife’s husband). The mayor’s announcement adds information in the sense that not only wife A knows that there is at least 1 cheater, she also knows that wife B is now aware of that fact as well.
When wife A sees the next day that wife B did not kill her husband even after the mayor announced that there was at least 1 cheater, she concludes than that wife B already knew that information and because wife A is not aware of any other cheating husbands she must conclude that wife B knows about husband A also being a cheat.
i thought the mayor was confessing his own infidelity – lol
Not as easy as it seems: equivalent to the blue eyed islanders paradox. The paradox is that on one hand this induction argument seems sound, but on the other hand, if there are n > 1 cheaters, the mayor’s announcement doesn’t seem to add any information.