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.
The mayor is a woman that is married to a man. There are only 2 married men in town. The other “married people” are women married to each other. The cheating man is the one not married to the mayor !!!
Doetoe,
The mayor’s announcement (for n>1) serves only as a reference to count the days so that women can synchronize: after day 1 since mayor’s announcement nothing happend, after day 2 nothing happened …
When the mayor makes the announcement, all the men in the town who were cheating all realize that they are now at risk of being killed. Very few things are more motivating than knowing that someone is about to kill you, so you take defensive action.
Here are two obvious defensive actions:
1. Leave the town immediately. Go far enough to not be found by pursuers.
2. Identify the people in the town who will likely participate in the (attempted) execution and kill them first.
I have to say I had to think for 5-10 minutes to understand the reasoning behind this solution, but on a small remark:
“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.”
As I think we should consider the day of the mayor annoucentment with n=0, the correct statment would be:
“Through induction, it can be proved that when this logic is applied to n cheating husbands, they all die on the n-1 th day after the mayor’s announcement.”
Best!
I am not with a new solution
But i think if we ask the Wives how many number of husbands are cheating in the city then the once telling the least number is being cheated … so they can kill them on the same day why to wait for those many.
Please correct me if I am wrong 🙂
” the mayor’s announcement doesn’t seem to add any information.”
This is an interesting part of the puzzle.
As noted on wikipedia for the blue-eyes puzzle,
“What’s most interesting about this scenario is that, for k > 1, the outsider is only telling the island citizens what they already know: that there are blue-eyed people among them. However, before this fact is announced, the fact is not common knowledge.”
I agree with badwolf. But I have another problem with the answer. In the situation with 2 cheaters, if the wives didn’t turn their husbands in right away they’d realize then, and not the next day, that both their husbands must be cheaters. I don’t see the logic in the answer.
I think only the cases when the major is a woman and announces 1 cheater, or when she announces more than 1 cheaters an the total number equals 2, could be resolved completely by the corresponding wives: there is no exchange of information among the wives other than the number of cheaters, and this information is assumed to be communicated individually to the major, who considers the true number of cheaters is the highest one.
Case 1) If the major is a cheater, he will not tell about himself, so:
1.i) If there is only 1 cheater, he willl announce there is no cheater: ok for his wife, as no other wife told her about her husband, not ok for the other wives, but as they cannot say anything to the major’s wife, she won’t find out.
1.ii) If there are 2 cheaters, he will say there is only 1: both the major’s wife and the other cheater’s will know only about 1 cheater, although the other cheater’s wife will only know about the major, so she could find out that since the major does not account himself and the number announce is 1, there must be a total of 2 cheaters and she only knows the identity of one, so she would find out the other one is her husband. However, the major’s wife would consider everything is allright when the other cheater is killed, because the major (her husband) said there is only 1 cheater, and 1 cheater has been executed.
1.iii) Only in case there are more than 2 cheaters, the major will be allowed to say the number of cheaters in greater than 1: in this case since the number of cheaters is n>2 and the cheaters’ wives know about n-1 cheaters, which remains bigger than 1, no cheater’s wife would notice.
Case 2) The major is not a cheater, but he is a man: since at least his wife can’t guess whether he is cheating (i.e. lying), the question would be resolved when he says n=1 or (n>1 and n=2), but his wife would not be certain, so I consider the situation is not fully resolved.
Case 3) The major is a woman:
3.i) If the major says n=1, then the wife who hasn’t heard of ay cheater will know it must be her husband.
3.ii) If the major says n>1 and there are just 2 cheaters, each cheater’s wife will know in that very moment that her husband is a cheater.
3.iii) If the major says n>1 and there are more than 2 cheaters, the cheaters’ wives will know about the n-1 cheaters (but n-1>1 because n>2), and the other wives will know about the n cheaters, but since no woman tells any other wife about her husband, no one would know if her husband is a cheater, since that would mean there are n+1 cheaters, which is still greater than 1.
I was just looking for this information for a while. After 6 hours of continuous Googleing, finally I got it in your website. I wonder what’s the Google’s problem that does not rank this kind of informative web sites closer to the top. Usually the top web sites are full of garbage.
So maybe I misunderstood something. If any given wife knows about ALL cheating husbands except her own, then you only need to ask 2 wives to find all cheating husbands. The first wife reveals all cheating husbands except her own. And the second wife can reveal whether or not the first wife’s husband was cheating.
The answer is that the Mayor (who is a girl) tells the town that he Husband is cheating. Therefore the Mayor’s husband dies.
ryn is right. You initially have assume what type of information, other than the mayor’s, is shared among wives.
If there is only one husband cheating, having just the number of other wives that know about a cheating husband is enough. For example, if a wife knows that 99 other wives know something but she doesn’t, then her husband must be cheating. On the other hand, if there are 2 or more cheaters, then every wife will know of some cheating husbands, but that information is not enough for her to conclude for sure if her own husband is cheating or not when the only other information is, according to the mayor, that there can possibly be more than one cheater.
If there are at least 2 cheating husbands, the crucial information that is needed, as ryn said, is the total number of cheating husbands, which can deduced if other wives share the exact number of cheating husbands that they know of. For example, if there are 2 cheating husbands, then 98 wives will know of 2 cheaters while 2 wives will know of only 1 cheater (a husband other than her own). If all that information is shared, then each of the last two wives, regardless of what the other wife does at the end of the day, can immediately conclude that her own husband is cheating since they both know that there are at least 2 cheaters but there are only 2 wives with the same situation of knowing only one cheater.
The same reasoning applies up to the maximum number of husbands. For the case of 99 cheating husbands, only 1 wife will know of 99 cheaters while 99 wives will know of 98 cheaters, thus those husbands belonging to the 99 wives must be cheating. For the case of 100 cheating husbands, all wives will know that there are 99 other cheating husbands, which can only mean that all husbands are cheating. The execution can actually occur on the same day for all the cases as soon as all the necessary information become available to all wives.
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).
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 :-). Fb however knows she’s done nothing wrong, so the only cheater can be her husband, so she promptly proceeds and kills Mb.
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.