What happens when the queen says "At least one man has cheated" - "Every woman immediately kills her husband".
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?
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.
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?
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.
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.
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.
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.
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.