Microsoft Interview Question Software Engineer / Developers
Day1: nothing happens. As every woman would be expecting that one of the men, she knows for adultery should die. No one would kill her own husband.
Day2: When no one dies, each woman would instantly come to know that her husband has cheated, and each woman would kill their husband. So everyone dies.
day1: nobody dies
day2: nobody dies
....
....
day100: since one one died so far and they are sure at least one is cheater, everyone dies on 100th day.
Every female knows only of the other males affairs, and thus none of them can kill their husband until day 100 like you suggest.
But I wonder if an acceptable answer would be day 1 everyone dies? These females could simply ask each other for their lists out of conspiracy, and thus doom the male population.
1st Night: If only one has cheated.
There is only one wife who has list of cheated husband count as zero and she kills her husband. One husband is killed.
2nd Night: If no killing happens 1st night.
The wifes with count of cheated husband as one, will kill their husbands. Two husbands are killed.
3rd Night: If no killing happens 2nd night.
The wifes with count of cheated husband as two, will kill their husbands. Three husbands are killed.
nth Night: If no killing happens (n-1)th night.
The wifes with count of cheated husband as (n-1), will kill their husbands. n husbands are killed.
This is a totally flawed argument. There is no requirement that cheating takes place *every* night. So even if only one person has cheated, the wife cannot determine that it was her husband *unless* she knows the exact number of cheaters. The only way the wives can know if their husband cheated is if they compare their count of last-nights-cheaters with each other. If another wife reports to have had sensed one more cheater, the first wife knows her husband cheated.
I do not think there is any woman with a cheat count less than 99, because the initial problem states that EVERY MAN HAS CHEATED. That means, every woman HAD A FEELING THAT SOMEBODY ELSE'S husband cheated (99).
this is the right explanation for the right answer.
@Conor: Deepak is not saying that the cheatings happen every night. All the cheatings have already happened. The nights only signify the fact that if a woman can prove that her husband has cheated, she must kill the husband before that day ends.
This is like a proof by induction. It is impossible to think about the 100 cheat case directly.
No one dies. Every woman already knows that at least one man has cheated. The queen is not providing any new information.
Your answer is true, but not complete. No one dies the first day, because each woman think the other 99 husbands should die(they know that already). The next they, since no husband has died, they know for sure each man must die.
>> The next they, since no husband has died, they know for sure each man must die.
So you say that following is correct: If a man was not executed until today it means that he didn't cheat before?
That couldn't be true, because if it was true women with who the man cheated would have to report that they have cheated, and they don't do this by the original condition (they only gossip with other women except the wife of the man they cheated with, and if they would report - the wife of the man they cheated with would have to know that their husband cheated (of the fact that he was executed), but she doesn't)
Actually, every woman EXCEPT 1 knew that a husband had cheated already, so when the queen announces a husband had cheated the only woman who didn't already know this would kill her husband. The reason the queen's announcement makes a difference is because before she announced it, the one woman who wasn't aware of her husband's cheating, didn't actually know for certain anyone had cheated.
let's simplify it
there are 2 married women: call them WA and WB
WA married to MA
WB married to MB
MA commits adultery with WB and WA does not know
MB commits adultery with WA and WB does not know
queen annouces to all that MA committed adultery and she has the proof then WA has to kill MA nd he's the only one killed end of story
however, if the queen herself is one of the 100 married women and the assumption is the rule of killing only applies when the woman herself can prove that her husband committed adultery ("Any wife who can prove that her husband is unfaithful must kill him") then the announcement by the queen ("announces that at least one husband has been unfaithful") is proof that her husband has cheated because there is no need to announce that someone elses husband has cheated because that is a known fact among these women ("Every wife in the village instantly knows when a man other than her husband has cheated") therefore the king will be killed on that faitfull day. :)
Agree with Dave. These are the facts:
- all men have cheated
- every woman knows, that all the other husbands, except for her own, have chated
- this means, that every of the 100 women knows, that 99 men have cheated (all others except her own husband)
- law prohibits adultery, and imposes the duty to kill the husband if he cheats THAT VERY DAY
- all women would never disobey the law -> means all the men had to cheat an their wifes with someone from outside the village, as no woman would cheat
- the only other person in the story is the visiting queen... she's visiting, meaning she's not from the village
- therefore, all the men cheated with the queen
- when the queen announces that at least one man has cheated, 99 women will know who it was, except for the one wife, who didn't know because it was her husband
- to this one wife, as this is news to her, it must have been her husband, because otherwise she would have known... and she kills her husband
it says: "Every wife in the village instantly knows when a man other than her husband has cheated."
but it also says: "AT LEAST one husband has been unfaithful." (emphasis on AT LEAST)
Therefore, anything from 1 to n husbands could have cheated that night.
If 1 husband cheated, on the day of the announcement, 99 women KNOW who cheated, or if you want, that a man, other than their own husband cheated !!! One woman is unaware that a cheating happened, because it was her own husband. As this is breaking news to her, she now knows that it was her husband (otherwise she would know that it was someone else) and has to kill him.
If 2 or more husbands cheated... let's suppose two (A and B) cheated, 100 wifes will know that at least one husband cheated, which is in line with the queen's announcement. Wife of A will be aware that B cheated, wife of B will be aware that A cheated. All other wifes will know that A and B have cheated, or that two other husbands have cheated. So if the queen says, at least one cheated, if 2 cheated, nothing will happen the first night. Every wife will be satisfied to know that it was someone else's husband. However, as noone dies that day, the following day, each woman will have doubts whether or not it was her husband or not. Every wife will know that it had to be more than one husband (because if it had been only one, he'd be dead by then). The wifes, however, will not know who, or how many husbands have cheated. Wife of any other husband X will know of A and B, but will be unsure if their own husband cheated as well or not. Wife of A will know, that B cheated, but as he's not dead, she will be unsure if her own husband cheated as well or not, cause it might have been any other husband as well. Because if 2 to 100 husbands cheat, every woman will not know if her husband cheated as well.
However, the law would not be applicable any more, because it states the wife has to kill the husband that very day (i.e. the day of the cheating). If two or more husbands cheat, noone dies the first day, and on the second day, the law is unapplicable.
if n>1 husbands cheat, the day of the announcement:
100-n wifes will know, that n husbands cheated
n wifes will know that n-1 husbands have cheated.
example: if 4 cheated, 96 wifes will know about the 4, and each of the 4 wifes cheated on will know about the 3 other cheating husbands.
no one dies the first night, as explained above, and the law becomes INAPPLICABLE (cf. "that very day").
should the law not become inapplicable. the second day, it depends whether the wifes are aware of the fact, that if two or more cheat, noone dies and they cannot prove it who it was. If they're aware of this consequence, nothing happens. If they're not aware of this consequence, very wife will think that one more husband than they're aware of have cheated... this can be only their own husband, and therefore each wife kill her husband. all husbands die.
the above example is actually valid for n>2;
because when n is 2, the first night, 98 women know that husbands A and B cheated and they know that therefore noone will die. however, the wife of A will expect B to die, and the wife of B will expect A to die. As this does not happen, both wifes of A and B will know there had to be one more, and the only coandidates are their respective husbands. Therefore, they will kill A and B.
what if three husbands have been unfaithful? no wife can expect anyone to die. 97 will know about 3 cheating husbands A,B,C. the three wifes will know only about 2 cheating husbands respectively. no wife can really expect anyone to be killed the first night. because they must know that the women have no proof. beyond this they will not obtain the proof. they know that no wife has the proof that their own husband cheated. on night two this doesn't change anything. each wife will know that no one died, because no one had a proof. the fact that no one died is no proof for the other wifes, as they should be aware of this.
the above example is actually valid for n>2;
because when n is 2, the first night, 98 women know that husbands A and B cheated and they know that therefore noone will die. however, the wife of A will expect B to die, and the wife of B will expect A to die. As this does not happen, both wifes of A and B will know there had to be more than one cheating husband, and the only candidates are their respective husbands. Therefore, they will kill A and B.
what if three husbands have been unfaithful? no wife can expect anyone to die. 97 will know about 3 cheating husbands A,B,C. the three wifes will know only about 2 cheating husbands respectively. no wife can really expect anyone to be killed the first night. because they must know that the women have no proof. beyond this they will not obtain the proof. they know that no wife has the proof that their own husband cheated. on night two this doesn't change anything. each wife will know that no one died, because no one had a proof. the fact that no one died is no proof for the other wifes either.
how does the queen's announcement help ? the wives knew beforehand that every husband other than their own has cheated. everyone is going for cases but how does it fit. there is just one case 100 husbands have cheated, nothing like if 1 husband cheated or 2 husbands cheated etc. there is just one case. if the wives know what they know, how does the queen's announcement that at least one husband has cheated help them in anyway. life does not work in cases. there is just one truth.
Facts:
All 100 men have already cheated that day.
Queen announces the fact that someone has cheated.
They do not know the identities of the cheater... just that someone has cheated.
If the woman can prove that her husband has cheated... she will kill him that day.
All the men die that day:
The only way of ever finding who cheated consistently no matter the number.. is to poll the women:
Raise your hand if you got notification... if someone didn't... that women would have the proof they needed.
If they all raise their hands... as they would in this case... then everyone dies.
The first thing to straighten out is that all women know that the others have the same powers as they do. i.e. they can all see all the cheaters except themselves. This must be so or it would not be possible in the 2 person scenario for the wives to deduce that the other sees their own cheating husband - otherwise they wouldn't know whether the other wife is just normal and doesn't see cheaters and so can't make any deductions of her own. Once this rule is established, you will see that if there are say 6 wives, they all know for sure there are either 5 or 6 cheaters. But when they think about their neighbour (i.e. any other wife) they say to themselves " If I'm not being cheated on, she must be wondering if there are in fact only 4 cheaters." Anyway, no matter, the wives know that they are all aware that there at least 4 cheaters. 4 cheaters is the minimum. REMEMBER THAT! So wife no. 1 looks to her neighbour and says to herself," If I'm not being cheated on, then she must be sitting there looking at the other 4 thinking, "If us two aren't being cheated on, then those 4 must know for certain that they are all being cheated on! That's because there are at least 4 cheaters! So they will all kill their husbands tonight!" But wife no.1 knows that won't happen. But she is disappointed (?!!) when her neighbour (ie every other wife!) doesn't kill her husband the night after that - only one explanation - they are all like her! So the next day (day3) all wives kill their husbands at once. It's the same with 100. The wives see 99, and know the minimum no. of cheaters "known" is 98. Day 1 they're all looking to their "neighbour" thinking, "Poor soul, I bet she thinks she's my buddy. She'll find out!" And she does, because everyone fails to conclude that they must be one of the 98. That's because they all see 99! But they don't see anything happen day 2 either, so they all conclude that nobody is seeing any "gaps" so they are all cheated!
The problem does not submit a legal definition of *proof of adultery*. I suppose we are to assume that consulting other women to find out and being told by them that one's husband is an adulterer is "proof".
There is also no mention of a law against lying, by either omission or commission.
The wording of the telepathy of the women is decidedly ambiguous. A woman knows when "a man other than her husband has cheated", sure: does she simultaneously know the identity of that man? Can she tell the difference between the infidelity of one man and another, both not her husband, when they cheat, or is the identity of the cheaters she sensed a secret?
For the sake of a solvable problem, we have to assume that the problem means each woman can detect when each specific man not her husband cheats, and thus each woman knows that at least EVERY MAN NOT HER HUSBAND in the village has cheated.
We must apparently also either assume (1) that each woman also knows of her blind spot concerning her husband, or we must assume (2) that she thinks herself in possession of a universal power of adultery detection.
If (1), then a reasonable assumption is that she would go ahead and ask her neighbor or BFF if her husband has cheated on her. I mean, she knows every guy but her husband has definitely cheated, and she knows she is blind to his cheating. So, she goes to her friends, and asks. They tell her. She kills him.
RESULT: All the men are dead when the queen comes to town.
If (2), Then every woman believes herself to be capable of telling, infallibly, when her husband cheats, and therefore falsely believes her husband to be faithful.
RESULT: The news brought by the queen is not new, and the husbands live on.
No one dies. Every woman already knows that at least one man has cheated. The queen is not providing any new information.
- Matt February 10, 2010