4 ms·

What happens when the queen says "At least one man has cheated" - "Every woman immediately kills her husband".

deleted 18y ago
[deleted]
tlrobinson 18y ago
Are you sure? If all 100 men have cheated then every woman already knows that 99 men have cheated, and the queen's announcement doesn't add any new information. Now, if the women can tell each other that they know 99 men cheated, then all women will instantly know their husbands cheated and must kill them (even before the queen makes her announcement). If they can't communicate, they have no way of knowing their own husband cheated (even after the queen makes her announcement, the "at least 1 husband" could have been any of the other 99, or hers, but she can't prove that). Or am I missing something?
- deleted 18y ago
  [deleted]
- mstoehr 18y ago
  The solution uses something called common knowledge, which is that everyone knows that everyone knows that every one knows, ad infinitum. Before the queen makes the announcement they may all know that the other husbands are cheating but they don't know if everybody else knows. To see the difference consider the case where there are only two husbands (H1, H2) and two wives (W1,W2). So, every man has cheated on his wife, and when the queen announces that a man has been unfaithful, then consider the situation from W1's perspective. She knows that H2 has cheated on W2, she doesn't know that H1 has cheated on her, and she can't talk to W2 about it. With the announcement, from her perspective, there are two possibilities (both H1 and H2 are cheaters), or (just H2 is a cheater). Now, to continue we need to think about what W1 will think about these two possibilities given her incomplete information: If it were possible world where (just H2 is a cheater) and H1 is honest, then since W2 would know that H1 hasn't cheated then W2 would conclude that (just H2 is a cheater) since at least one husband had cheated. Thus, by the laws of the island W2 would kill H2 the day of the announcement. Since W1 considers it a possibility that her husband, H1, was faithful, she won't do anything the first day; instead she'll just wait to see whether W2 kills H2. By symmetry W2 will go through the same line of reasoning about W1. Thus, both will do nothing the first day. So then on the second day, W1 will realize that (just H2 is a cheater) must be false, since W2 didn't kill H2. So, she'll go ahead and kill W1. (Apply the same reason symmetrically to W2). Therefore, they'll both kill their husbands on the second day. The rest of the details are pretty easy to establish. The point is that 99 days later all the men are killed.
  - globalrev 18y ago
    But if they can talk to each other about it they would have killed all the man before the queen came.
    - jcl 18y ago
      ...which is why it's implicit in the problem's statement that they can not talk to each other about it.
  - tlrobinson 18y ago
    I had to read that twice but I think I got it. However, I don't see why it takes 99 days for them to all be killed. If all 100 men have cheated then there's no "asymmetry", so which wife kills her husband first? Wouldn't they have to kill all the husbands at the same time or not at all?
- YuriNiyazov 18y ago
  I took the following assumptions: 1) The women can't tell each other anything 2) Every woman knows the following fact: "every woman knows when a husband other than her own cheated". Now, let's simplify the problem and say that there are only 3 women as opposed to 100, and assign numbers to them and their respective husbands. Woman #3 thinks "I know that husband #1 and husband #2 cheated. Woman #2 knows that husband #1 cheated. Woman #1 sees that woman #2 and I (woman #3) are not killing our husbands, which logically would mean that her husband is the cheater. However, she (Woman #1) is capable of going through this thought process, and is yet not killing her husband. That means that she is thinking of either husband #2 or my husband (#3) as the cheater. Yet, woman #2 is capable of going through this thought process as well, and if my (#3) husband was not a cheater, then woman #2 would've killed her husband. Yet she hasn't, which means that my husband (#3) is the cheater. So, I have to go kill him". Now, there was nothing special about woman #3 - every woman goes through this thought process simultaneously, and all arrive at the same conclusion. Now, expand to 100. Maybe my explanation is a little muddy, and I am not giving enough justification to the last step of "simultaneous thought process", but I am pretty sure that this is the right method for solving the problem.
  - jcl 18y ago
    The problem states that "Any wife who can prove that her husband is unfaithful must kill him that very day." There's no requirement that a wife must kill her husband as soon as she knows; she can postpone it at least to midnight, if she felt so inclined. Since a woman can't be sure that any other woman is planning a killing until the next day, the massacre takes place on the 100th day, not immediately.
globalrev 18y ago
Hmm I am not sure about this one. With 2 couples it goes: Both women know that the other man has cheated but they don't know if their own has. So when the queen says one has cheated at first they don't kill their husbands becuase it could be the other one. But if the other woman didn't know the others man had cheated the cheater had to be their own but since she didn't she must know the other has cheated. So they will both kill their husband after figuring that out. But i am not sure this is the same for 3 and more couples. Can they make the same deduction? If the queen said that 99 other men had cheated, yes, but 1? I don't see it.
- jcl 18y ago
  It does indeed extend to three or more, as others have outlined above. For three couples: On the first day, nothing happens, which surprises no one, since all the wives know there are multiple guilty parties. On the second day, nothing happens again. A wife reasons: "If my husband were innocent, then the other two wives would see only each other's husbands as cheaters, which is the same situation as if me and my husband were not on the island at all. By the logic of the two-cheating-couple case, they should then have killed their husbands today. Since they did not, my husband must have cheated, too." Thus, all the wives kill their husbands on the third day. The logic extends easily to more couples.
deleted 18y ago
[deleted]
lfasonar 18y ago
Not true. After 99 days, every woman kills her husband. Consider the case with two couples, (1) and (2). (1) knows that (2) cheats, so when the queen says that at least one man has cheated, (1) knows of two possibilities: either [a] only (2) has cheated or [b] both (1) and (2) have cheated. If [a] is true, then (2) will immediately know (2) cheated, since she knows that (1) has not cheated. Thus, if by the end of the first day, (2) has not killed her husband, (1) knows that [b] must be true. The numbering is arbitrary, so every woman kills her husband after one day. Now consider the case of 3 couples (1), (2), and (3). From the point of view of (1), (2) and (3) have cheated. (1) also knows that (2) knows whether (1) has cheated or not, so (1) considers what (2) is thinking: "(2) either sees that [a] (1) and (3) have cheated or [b] that only (3) has cheated. If [b] is true, then (2) will be able to figure out whether (2) has cheated like this: since [b] is true, (3) will kill her husband on day 1 if (2) has not cheated. If she has not, then (2) must have cheated. If however, [a] is true, no one will have killed their husband after 2 days" Therefore (1) waits 2 days and kills her husband.

deleted 18y ago

[deleted]

Are you sure? If all 100 men have cheated then every woman already knows that 99 men have cheated, and the queen's announcement doesn't add any new information. Now, if the women can tell each other that they know 99 men cheated, then all women will instantly know their husbands cheated and must kill them (even before the queen makes her announcement). If they can't communicate, they have no way of knowing their own husband cheated (even after the queen makes her announcement, the "at least 1 husband" could have been any of the other 99, or hers, but she can't prove that). Or am I missing something?

deleted 18y ago
[deleted]
mstoehr 18y ago
The solution uses something called common knowledge, which is that everyone knows that everyone knows that every one knows, ad infinitum. Before the queen makes the announcement they may all know that the other husbands are cheating but they don't know if everybody else knows. To see the difference consider the case where there are only two husbands (H1, H2) and two wives (W1,W2). So, every man has cheated on his wife, and when the queen announces that a man has been unfaithful, then consider the situation from W1's perspective. She knows that H2 has cheated on W2, she doesn't know that H1 has cheated on her, and she can't talk to W2 about it. With the announcement, from her perspective, there are two possibilities (both H1 and H2 are cheaters), or (just H2 is a cheater). Now, to continue we need to think about what W1 will think about these two possibilities given her incomplete information: If it were possible world where (just H2 is a cheater) and H1 is honest, then since W2 would know that H1 hasn't cheated then W2 would conclude that (just H2 is a cheater) since at least one husband had cheated. Thus, by the laws of the island W2 would kill H2 the day of the announcement. Since W1 considers it a possibility that her husband, H1, was faithful, she won't do anything the first day; instead she'll just wait to see whether W2 kills H2. By symmetry W2 will go through the same line of reasoning about W1. Thus, both will do nothing the first day. So then on the second day, W1 will realize that (just H2 is a cheater) must be false, since W2 didn't kill H2. So, she'll go ahead and kill W1. (Apply the same reason symmetrically to W2). Therefore, they'll both kill their husbands on the second day. The rest of the details are pretty easy to establish. The point is that 99 days later all the men are killed.
- globalrev 18y ago
  But if they can talk to each other about it they would have killed all the man before the queen came.
  - jcl 18y ago
    ...which is why it's implicit in the problem's statement that they can not talk to each other about it.
- tlrobinson 18y ago
  I had to read that twice but I think I got it. However, I don't see why it takes 99 days for them to all be killed. If all 100 men have cheated then there's no "asymmetry", so which wife kills her husband first? Wouldn't they have to kill all the husbands at the same time or not at all?
YuriNiyazov 18y ago
I took the following assumptions: 1) The women can't tell each other anything 2) Every woman knows the following fact: "every woman knows when a husband other than her own cheated". Now, let's simplify the problem and say that there are only 3 women as opposed to 100, and assign numbers to them and their respective husbands. Woman #3 thinks "I know that husband #1 and husband #2 cheated. Woman #2 knows that husband #1 cheated. Woman #1 sees that woman #2 and I (woman #3) are not killing our husbands, which logically would mean that her husband is the cheater. However, she (Woman #1) is capable of going through this thought process, and is yet not killing her husband. That means that she is thinking of either husband #2 or my husband (#3) as the cheater. Yet, woman #2 is capable of going through this thought process as well, and if my (#3) husband was not a cheater, then woman #2 would've killed her husband. Yet she hasn't, which means that my husband (#3) is the cheater. So, I have to go kill him". Now, there was nothing special about woman #3 - every woman goes through this thought process simultaneously, and all arrive at the same conclusion. Now, expand to 100. Maybe my explanation is a little muddy, and I am not giving enough justification to the last step of "simultaneous thought process", but I am pretty sure that this is the right method for solving the problem.
- jcl 18y ago
  The problem states that "Any wife who can prove that her husband is unfaithful must kill him that very day." There's no requirement that a wife must kill her husband as soon as she knows; she can postpone it at least to midnight, if she felt so inclined. Since a woman can't be sure that any other woman is planning a killing until the next day, the massacre takes place on the 100th day, not immediately.

globalrev 18y ago

Hmm I am not sure about this one. With 2 couples it goes: Both women know that the other man has cheated but they don't know if their own has. So when the queen says one has cheated at first they don't kill their husbands becuase it could be the other one. But if the other woman didn't know the others man had cheated the cheater had to be their own but since she didn't she must know the other has cheated. So they will both kill their husband after figuring that out. But i am not sure this is the same for 3 and more couples. Can they make the same deduction? If the queen said that 99 other men had cheated, yes, but 1? I don't see it.

jcl 18y ago
It does indeed extend to three or more, as others have outlined above. For three couples: On the first day, nothing happens, which surprises no one, since all the wives know there are multiple guilty parties. On the second day, nothing happens again. A wife reasons: "If my husband were innocent, then the other two wives would see only each other's husbands as cheaters, which is the same situation as if me and my husband were not on the island at all. By the logic of the two-cheating-couple case, they should then have killed their husbands today. Since they did not, my husband must have cheated, too." Thus, all the wives kill their husbands on the third day. The logic extends easily to more couples.

deleted 18y ago

[deleted]

lfasonar 18y ago

Not true. After 99 days, every woman kills her husband. Consider the case with two couples, (1) and (2). (1) knows that (2) cheats, so when the queen says that at least one man has cheated, (1) knows of two possibilities: either [a] only (2) has cheated or [b] both (1) and (2) have cheated. If [a] is true, then (2) will immediately know (2) cheated, since she knows that (1) has not cheated. Thus, if by the end of the first day, (2) has not killed her husband, (1) knows that [b] must be true. The numbering is arbitrary, so every woman kills her husband after one day. Now consider the case of 3 couples (1), (2), and (3). From the point of view of (1), (2) and (3) have cheated. (1) also knows that (2) knows whether (1) has cheated or not, so (1) considers what (2) is thinking: "(2) either sees that [a] (1) and (3) have cheated or [b] that only (3) has cheated. If [b] is true, then (2) will be able to figure out whether (2) has cheated like this: since [b] is true, (3) will kill her husband on day 1 if (2) has not cheated. If she has not, then (2) must have cheated. If however, [a] is true, no one will have killed their husband after 2 days" Therefore (1) waits 2 days and kills her husband.