Couples Therapy
OK, I opened Pandora’s Box with this post, so I might as well close it. (You’ll have to read the post and skim the comments to get up to speed.)
In the below, I’ll walk through the analysis for the village having a total of one, two, and three couples. (Note that the couples have very convenient names.) You’ll see the pattern I hope, and then realize why the solution works for all 100 wives killing their husbands on Day 100 in the original version.
VILLAGE HAS 1 COUPLE ==> ALL MEN DIE ON DAY 1
=============================================
Alice doesn’t know that Alan has been unfaithful to her. (Don’t ask me how he did it if she’s the only woman.) So clearly, Alice won’t kill Alan. But then the Queen says, “At least one husband has cheated in this village.” Alice realizes the Queen must be referring to Alan, so she kills him on Day 1.
VILLAGE HAS 2 COUPLES ==> ALL MEN DIE ON DAY 2
==============================================
Alice knows that Bill cheated on Betty, and Betty knows that Alan cheated on Alice. However, nobody kills anybody, because neither wife is sure that her own husband has cheated. Then the Queen says, “At least one husband has cheated in this village.” Now at first, the wives are still uncertain. For example, Alice can’t kill Alan, because for all she knows, Bill is the cheater to whom the Queen refers. However, if Day 1 comes and goes, now Alice *can* be sure. She reasons, “If Betty never saw Alan cheating on me, then the Queen’s announcement would make Betty sure that Bill had been the cheater. So Betty would have killed Bill on Day 1. However, since Betty did *not* kill Bill on Day 1, I can conclude that Betty saw Alan cheat on me.” Therefore, on Day 2, Alice kills Alan. By similar logic, Betty kills Bill.
VILLAGE HAS 3 COUPLES ==> ALL MEN DIE ON DAY 3
==============================================
Alice knows that Bill and Charlie cheated, Betty knows that Alan and Charlie cheated, and Cindy knows that Alan and Bill cheated. Further, Alice knows that Betty knows that Charlie cheated. However, Alice does NOT know that Betty knows that Cindy knows that Bill OR Alan cheated. In other words, Alice cannot be sure that Betty knows that Cindy knows “at least one husband in this village has cheated.” In still other words, Alice realizes it is possible that Betty believes that Cindy has observed 0 instances of adultery.
Clearly, without the Queen, nobody has any reason to kill anyone.
However, things change once the Queen says, “At least one man in this village has cheated.” If there a woman who started out having observed 0 instances of adultery, then that woman would kill her husband during Day 1. Thus, when Day 1 comes and goes with no murder–AFTER the Queen’s announcement–it changes Alice’s knowledge. In addition to everything she had directly observed, and then deduced, at the outset, Alice can now conclude, “Betty knows that Cindy has observed at least one instance of adultery.” To reiterate, this is new knowledge, and shows that the Queen’s announcement, plus the subsequent actions, adds new knowledge.
However, after Day 1 has passed, there is still not enough for any woman to kill her husband. For example, Alice still can’t be sure that her own husband, Alan, has cheated on her. Alice knows that Betty and Cindy have each observed at least one act of adultery (otherwise they would have killed their husbands on Day 1), but perhaps Betty merely saw Charlie, and Cindy merely saw Bill. Notice, though, that if Betty ONLY saw Charlie, then Betty would kill Bill during Day 2 (not Day 1). That’s because Betty would know by Day 2 that Cindy had observed at least one act of cheating, and so–if Betty had never witnessed Alan cheating–then she would deduce that Cindy must have seen Bill cheating.
But if Day 2 comes and goes as well, then Alice realizes that Betty must have observed Alan cheating; this is why Betty couldn’t be confident in killing Bill on Day 2. Thus by Day 3, Alice realizes Alan cheated and kills him. The other wives go through similar reasoning, and kill Bill and Charlie on Day 3 as well.
By similar reasoning, if there are 100 couples, nobody makes a move until Day 100, at which time all 100 husbands see the end.
OK, I get all that. It works out perfectly in my mind if you stick to 3 couples or less. But once you add more it doesn’t make sense anymore. For example, do you agree with me that in a 4 couple scenario that every woman saw 3 cheaters? And that woman 1 knows for sure that every other woman saw 2 cheaters? And that woman 1 knows for certain that every other woman knows that every other woman saw 1 cheater?
Yes, all of that is true. Woman 1 knows that Woman 2 knows that Woman 3 has seen at least one cheater, namely Man 4. But that doesn’t mean that Woman 1 knows that Woman 2 knows that Woman 3 knows that Woman 4 has seen any cheaters.
Here’s the thing: Woman 1 thinks it’s possible that Woman 2 thinks it’s possible that Woman 3 thinks the following: “I have only seen one cheater, Man 4. It’s possible that he’s the only cheater. If he is the only cheater, then since Woman 4 doesn’t know that she’s being cheated on, Woman 4 may think that there is no cheating going on in the village.”
Ok, that makes sense to me. Let me try it with five now to see if it is sinking in.
OK, and it makes sense to say that for 5 groups, too. Hmm… I think it is clicking now.
Great! So are you now convinced that in the hundred-couple case, Woman 1 thinks it’s possible that Woman 2 thinks it’s possible that … Woman 100 sees no cheating?
I think it does, but I need to come back to this when I can give it my undivided attention. Coming back to it off and on as I do other things keeps throwing me off.
Oh man Dan, I thought for sure if you saw it worked for 1 through 3, you would realize it had to work for N couples.
Just reduce all of your numbers by 1, and see that they hold for the 3-couple scenario. So that’s why nobody dies on Day 2, but they all die on Day 3. Likewise, for 4 couples, nobody dies on Day 3, but they all die on Day 4.
No, I really haven’t thought through on which day they would kill their husbands, yet. I’m not denying you are right that they would all act on day 100. I’d need to think more on that before I could tell you if that made sense to me or not. I’m trying to understand how it could be possible for them to reason that there is a progression where one woman believes that another woman thinks nobody cheated. Keshav agreed with me that in a 4 group scenario that woman 1 knows for certain that every other woman knows that every other woman saw 1 cheater. So it makes no sense to me to say that every woman knows with 100% certainty that every other woman knows every woman saw at least one cheater, and then to do a progression where any of them think it is possible to believe one woman believes nobody cheated.
Dan, Woman 1 knows that Woman 2 knows that Woman 3 has seen at least one cheater. But that doesn’t mean that Woman 1 knows that Woman 2 knows that Woman 3 knows that everyone has seen at least one cheater, does it?
Of course, it’s all predicated on each wife being guaranteed to see everyone else’s husband cheat and knowing that is true for every other wife in the village. Otherwise, you can’t know if you happening to see no cheating means your husband did, nor the “fact” that if the other wives don’t kill their husbands they saw another cheater.
This all reminds me of the great “You Can Burden the Future With Debt”. No matter how carefully you explain every step, people will still deny the logic.
This is usually known as “the blue-eyed islanders” puzzle. The proof by induction is correct.
“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 think they all die as soon as the announcement is made, because if you can deduce the logic that shows every man cheated, then so can they. Why wait the 100 days when the outcome is inevitable?
If the Queen makes this announcement and no husbands have cheated, all husbands will be killed on day 1.
Also, keep in mind that the number of cheaters does not need to be equal to the total number of couples for this to work. If there are 25 cheaters in a village of 100 couples, all of and only the cheating men will be killed on day 25.