Harder Interview Question #2

[slickpoppa]

Here is another one of my favorites:

Every man in a village of fifty couples has been unfaithful to his wife. Every woman in the village is instantly told by another villager when a man other than her husband has cheated, but not when her own husband has. The village's no-tolerance adultery statute requires that a woman who can prove her husband has been unfaithful must kill him that very day. No woman would ever disobey this law. Every woman in the village also instantly knows when one of these killings has occurred. One day, the queen, who is known to be infallible, visits the village. She announces that at least one husband has been unfaithful. What happens? Assume that all of the women are completely logical (A wild assumption of course)

Hint: The answer involves when things happen

[RocketManJames]

Since I failed miserably on Question #1... lemme try this one.

I tried it for 2 couples and 3 couples, and after some thought I think that what happens is...

All the cheating husbands are killed on Day N after queen announces. N = # of cheaters. I am too tired to type out why, but I did work this out (honestly).

-RMJ

[pzhon]

[ QUOTE ]
One day, the queen, who is known to be infallible, ...
Assume that all of the women are completely logical

[/ QUOTE ]
Your statement of that problem is incomplete for the usual solution. You have to assume not only that the queen is known to be infallible, but also that fact is known, and that fact is known, etc. You can't let someone know the queen is infallible, but doubt whether everyone else knows this, or doubt whether everyone knows that no one has a doubt about the queen's infallibility, etc.

You have to assume that the women are not only logical, but know that the other women are logical, and know that they know that the other women are logical, etc.

[slickpoppa]

[ QUOTE ]
Your statement of that problem is incomplete for the usual solution. You have to assume not only that the queen is known to be infallible, but also that fact is known, and that fact is known, etc. You can't let someone know the queen is infallible, but doubt whether everyone else knows this, or doubt whether everyone knows that no one has a doubt about the queen's infallibility, etc.

You have to assume that the women are not only logical, but know that the other women are logical, and know that they know that the other women are logical, etc.

[/ QUOTE ]
Yeah, all of those assumptions are necessary. I thought that they were implied, but maybe I should have been more explicit.

[Matt Flynn]

all men are killed.

[slickpoppa]

[ QUOTE ]
all men are killed.

[/ QUOTE ]
Hint: The answer involves when things happen

Remember, this is an interview question. You have to explain WHY. Anyone can just guess that all of the men die.

[Rasputin]

Not looking at previous answers:

Fifty men have been unfaithful.

Fifty women have each been told 49 of the other husbands have been unfaithful.

If only one mad had been unfaithful, he would be killed that day because there would have been only one woman who hadn't heard about any infidelity.

If only two had been unfaithful, two women would have only heard of one infidelity. At midnight when they knew there were no killings, that woman would know that the wife of the man she knew was a cheater had heard of an infidelity. Since this woman had only heard of one, she must conclude that her husband was number two.

If there were three, then the first two nights would go by without killings because there would be three women who knew about two.

So counting the day of the announcement as day 1 as each day goes by without a killing, the women know that more and more men have been unfaithful and that number is equal to the number of the day. Day one they know one man has. Day two they know two men have.

At midnight on day 50 every woman knows that every man has been unfaithful and the women kill them all.

[shummie]

I think the answer to this is easy. All 50 guys have cheated. The wives know about everyone elses cheating. So they know that besides their husband all other 49 guys in the tribe have cheated. That leaves them with two options:

1) Their husband is a cheat in a tribe of cheaters.
2) Their husband is the ONLY guy in the tribe who isn't cheating.

You make the call.

[Paul2432]

I read the solution, but I am having trouble with one part. Each woman knows the other 49 husbands are cheaters. Hence each woman knows that "at least one of the husbands is a cheater" and also knows that each woman knows this. The queen has provided no new information. So why aren't all the husbands dead already?

Paul

[RocketManJames]

I should learn to read... The first sentence didn't sink in, I didn't realize that ALL the men were cheaters. I think my answer is correct for the generalized problem, where you don't know how many cheaters there were. For 50 cheaters, they all die on day 50. For N cheaters, they all die on day N (the day the cheated-on women all find out at once that their husbands cheated).

-RMJ

[Rasputin]

[ QUOTE ]
I read the solution, but I am having trouble with one part. Each woman knows the other 49 husbands are cheaters. Hence each woman knows that "at least one of the husbands is a cheater" and also knows that each woman knows this. The queen has provided no new information. So why aren't all the husbands dead already?

[/ QUOTE ]

If you're a woman and know that 49 men have cheated you're in one of two situations. 1) All the men have cheated so there are 50 women who each know that 49 men have cheated. 2) 49 men have cheated so there are 49 women who know that 48 men have cheated, and one woman that knows that 49 have.

Until there is a way to logically deduce that one situation is reality, everything is in limbo as there is plausible deniability.

Now imagine that the queen had said that there are at least 49 men who have been unfaithful. You know of 49 who have been unfaithful so you don't kill your husband. You know that if any of the other women in the village only know of 48 men who have been unfaithful that they will be forced to conclude that their husband is #49 and kill him. When that doesn't happen you now know that none of the other women could deduce that their husband was unfaithful. Therefore, none of the other women knew of just 48 men who had been unfaithful. Therefore, all of the other women knew of 49 and since they never know their own husbands are unfaithful if another woman knows of 49 then your husband was unfaithful.

If the queen had said that there were forty eight men who had been unfaithful then you as a woman knowing that 49 were wouldn't be concerned. When no men are killed that night you know that everyone already knew of at least 48 and you can deduce that there are forty nine. Since you have already heard of forty-nine you are not concerned. When another night goes by you know that everyone else knew of forty-nine and you start sharpening the steak knives.

It all goes back to the theoretical situation where there is one cheater and one wife who knows of know cheaters. Until she knows that there is a cheater she has no reason to kill her husband. Once she finds out that there is one she must conclude that it's her man and kill him.

[slickpoppa]

[ QUOTE ]
[ QUOTE ]
I read the solution, but I am having trouble with one part. Each woman knows the other 49 husbands are cheaters. Hence each woman knows that "at least one of the husbands is a cheater" and also knows that each woman knows this. The queen has provided no new information. So why aren't all the husbands dead already?

[/ QUOTE ]

If you're a woman and know that 49 men have cheated you're in one of two situations. 1) All the men have cheated so there are 50 women who each know that 49 men have cheated. 2) 49 men have cheated so there are 49 women who know that 48 men have cheated, and one woman that knows that 49 have.

Until there is a way to logically deduce that one situation is reality, everything is in limbo as there is plausible deniability.

Now imagine that the queen had said that there are at least 49 men who have been unfaithful. You know of 49 who have been unfaithful so you don't kill your husband. You know that if any of the other women in the village only know of 48 men who have been unfaithful that they will be forced to conclude that their husband is #49 and kill him. When that doesn't happen you now know that none of the other women could deduce that their husband was unfaithful. Therefore, none of the other women knew of just 48 men who had been unfaithful. Therefore, all of the other women knew of 49 and since they never know their own husbands are unfaithful if another woman knows of 49 then your husband was unfaithful.

If the queen had said that there were forty eight men who had been unfaithful then you as a woman knowing that 49 were wouldn't be concerned. When no men are killed that night you know that everyone already knew of at least 48 and you can deduce that there are forty nine. Since you have already heard of forty-nine you are not concerned. When another night goes by you know that everyone else knew of forty-nine and you start sharpening the steak knives.

It all goes back to the theoretical situation where there is one cheater and one wife who knows of know cheaters. Until she knows that there is a cheater she has no reason to kill her husband. Once she finds out that there is one she must conclude that it's her man and kill him.

[/ QUOTE ]Yeah, that pretty much nails it

[gaming_mouse]

[ QUOTE ]
If you're a woman and know that 49 men have cheated you're in one of two situations. 1) All the men have cheated so there are 50 women who each know that 49 men have cheated. 2) 49 men have cheated so there are 49 women who know that 48 men have cheated, and one woman that knows that 49 have......

[/ QUOTE ]

Nice work. This can be made rigorous by induction on N.

Theorem. If every woman knows that at least N men have cheated and does not know that her own husband has cheated, then a total of N+1 men must have cheated.

Proof Assume the opposite. That is, the assumption of the theorem holds, and yet only N men (or fewer) have actually cheated. Consider the wives of the N men who have cheated. Each of them can clearly know of only N-1 who have cheated -- otherwise they would know of their own husband's indidelity. This contradiction proves the theorem.

As logical creatures, every woman in the tribe is aware of the above Theorem. The queen's announcement gives us the seed case of N=1. It follows by induction that all men will be killed.

[TomCollins]

What is the point of the queen?

Every woman already knows that at least 1 person cheated.

[gaming_mouse]

[ QUOTE ]
What is the point of the queen?

Every woman already knows that at least 1 person cheated.

[/ QUOTE ]

But they don't know that this fact is common knowledge, in the technical sense of the term.

It means that you know that everyone else knows, and they know that you know that fact, and you know that they know that you know that fact, and so on, ad infinitum.

There will not be common knowledge that "at least one husband has cheated" until the queen's announcement.

gm

[Paul2432]

[ QUOTE ]
[ QUOTE ]
What is the point of the queen?

Every woman already knows that at least 1 person cheated.

[/ QUOTE ]

But they don't know that this fact is common knowledge, in the technical sense of the term.

It means that you know that everyone else knows, and they know that you know that fact, and you know that they know that you know that fact, and so on, ad infinitum.

There will not be common knowledge that "at least one husband has cheated" until the queen's announcement.

gm

[/ QUOTE ]

Why not? If all men have cheated (a given in the problem) then each woman knows that the 49 other husbands have cheated. In this situation it would be impossible for every woman not to know that at least one husband has cheated and for each woman to know this, etc.

Paul

[TomCollins]

If you know that 49 people have cheated, there are two cases. 1) Your husband did not cheat and everyone else did. You also know that everyone else knows of at least one other cheater.
2) Your husband did cheat as well, so you know there is a cheater. You also know the other women know there is at least one.

Every woman is in this position. Every woman knows there is at least one cheater. I still don't understand what the queen adds.

[gaming_mouse]

[ QUOTE ]

Every woman is in this position. Every woman knows there is at least one cheater. I still don't understand what the queen adds.

[/ QUOTE ]

Yes, but this is not the same as common knowledge. I have to think about how to explain why it is not, and I'll post again later. Or maybe someone else can explain it....

However, the queen's statement is necessary.

gm

[RocketManJames]

[ QUOTE ]
If you know that 49 people have cheated, there are two cases. 1) Your husband did not cheat and everyone else did. You also know that everyone else knows of at least one other cheater.
2) Your husband did cheat as well, so you know there is a cheater. You also know the other women know there is at least one.

Every woman is in this position. Every woman knows there is at least one cheater. I still don't understand what the queen adds.

[/ QUOTE ]

Think of it as a reset. Before the queen's announcement, none of the women have a sense of WHEN each of the other women were made aware of this "common knowledge." So, the queen's decree is a reset of sorts that resets the timer to 0, which marks the time at which all women's knowledge clocks are started.

-RMJ

[gaming_mouse]

[ QUOTE ]
Think of it as a reset. Before the queen's announcement, none of the women have a sense of WHEN each of the other women were made aware of this "common knowledge." So, the queen's decree is a reset of sorts that resets the timer to 0, which marks the time at which all women's knowledge clocks are started.

[/ QUOTE ]

WHEN has nothing to do with it. The puzzle would be exactly the same if all the women cheated at the same time and found out about all the other women at the same time.

Here is the difference between common knowledge and the kind of knowledge every women has before the queen's announcement.

With commom knowledge, there exists one man (it doesn't matter that they don't know which man specifically) about whose infedelity ALL 50 women share knoweledge.

Before the queen's announcment, we have the following state of affairs:

Women {2-49} have common knowledge that woman1's husband cheated.

Women {1,3-49} have common knowledge that woman2's husband cheated.

etc.

However, there exists no man whose infedelity is common knoweledge for ALL 50 women. This man's existence is the key to undermining each woman's plausible deniability, and is therefore the reason the queen's announcement is needed.

gm

[TomCollins]

GM, your answers are usually so clear, I just am not getting this. Every woman can deduce that every woman knows someone cheated. And every woman knows that every woman knows this.

So every woman knows that some man exists that cheated.

[gaming_mouse]

[ QUOTE ]
So every woman knows that some man exists that cheated.

[/ QUOTE ]

That is true. But they don't know it's the same man that they all know about. There has to be ONE man who they ALL KNOW cheated (more precisely, a single man whose infedelity is common knowledge).

Does that make sense?

[RocketManJames]

GM...

You're absolutely right. I just re-thought about it after what you said and it's clear in the case of 2 couples. I guess I just suck at this type of thinking...

If you have 2 women who each have a cheating husband... they each know that at least one husband is a cheater, but neither is sure of what the other one knows. So, as a result, both could possibly live in a state where there was 1 cheater, and they'd each know what they knew.

Case with 2 couples (no queen announcement):

Wife 1: Knows Wife 2's husband cheated.
Wife 2: Knows Wife 1's husband cheated.

Can happen if: Both husbands are cheaters or exactly the other husband is a cheater.

Case (with Queen announcement):

Wife 1: Knows Wife 2's husband cheated. Also, knows that Wife 2 knows that a husband has cheated. This was the thing that was not known, since now each woman KNOWS that they had to have heard of a cheating, else it becomes clear that she was cheated upon.

Wife 2: Thinks the same as above.

Thanks, GM. You are totally right, and I'm a moron.

-RMJ

[TomCollins]

The queen tells them the specific man, or just that one man in general cheated. I guess thats what is confusing me.

[gaming_mouse]

[ QUOTE ]
The queen tells them the specific man, or just that one man in general cheated. I guess thats what is confusing me.

[/ QUOTE ]

No, she just told them one man in general cheated. They don't have to know who it is. But there now exists at least one man who everybody knows cheated. That they do not know his name is of no consequence. The point is, before the queen's announcement, there was no such man. There existed men whose infidelity was known to 49 women, but there was never one whose infedelity was known to all 50. After the queen's announcement, there is.

[tylerdurden]

[ QUOTE ]

Wife 1: Knows Wife 2's husband cheated. Also, knows that Wife 2 knows that a husband has cheated. This was the thing that was not known, since now each woman KNOWS that they had to have heard of a cheating, else it becomes clear that she was cheated upon.

[/ QUOTE ]

A (possibly) clearer explanation in the case of two wives:

The queen makes her announcement. W1 knows H2 cheated, but doesn't know that H1 cheated (and therefore doesn't know that W2 knows that H1 cheated). If H1 had *not* cheated, then W2 would know that he hadn't, since W2 finds out instantly when any H other than H2 cheats. Therefore if W2 finds out a man is cheating, she will kill her own husband *if* she knows that H1 is *not* cheating. Since she knows that H1 *is* cheating, however, she can assume the queen was speaking about H1.

W1 therefore waits to see if W2 kills her husband the day of the queen's announcement. If she doesn't, the W1 has to assume that her husband is also cheating.

W1 and W2 both kill their husbands on the day after the announcement.

[Rasputin]

[ QUOTE ]
So every woman knows that some man exists that cheated.

[/ QUOTE ]

They don't need to know that one man cheated, they need to know that 50 men cheated. They know that either 49 men have cheated, or 50 men have cheated. They have no way of proving that the fiftieth man cheated. The Queen's statement gives them a way.

Do you understand the logic that says if there was one man who cheated, he would die as soon as the Queen made her statement?

Do you understand the logic that says if there were two men who cheated, they would die as soon as the first midnight passed after the Queen's statement?

When the Queen makes her statement, all the women are in the same position. They know that either 49 or 50 men have cheated. They know that if they count the days that pass without a killing, they can determine whether it is 49 or 50.

Think about it the way it would have happened in real life. You're a woman. You're married, all the rules apply.

Someone tells you that so and so's husband cheated. Three weeks later someone else tells you that someone else's husband cheated. A month later someone comes and says that someone else's husband cheated. Eventually you hear about 49 men who have cheated. At no point have you been given enough proof that their husband has cheated.

[TomCollins]

I finally got it. Otherwise the killings would never start. Even if I know 49 people cheated, I don't know whether the other people would know enough to kill their husband. Start with the simplest case of 3 people.

I know B and C cheated. There are two possibilities:

1) B knows A and C cheated, C knows B and A cheated.

2) B knows C cheated, C knows B cheated.

I'm not sure which one.
If its case #2, B has no way of knowing that she has been cheated on, and C has know way of knowing she has been cheated on. So they both wait.

Now the possibilities for B (and C)
B knows that one of 2 subpossibilities exist

1) C knows nothing
2) C knows B cheated.

Without the queen, subpossibilitiy 1.1 can exist. So the wife can kill her husband the first night. Without her, no one could have begun the killing.

But this possibility does not happen the first night.

This same principle should apply to 50 women.

Hope this straightened things out for anyone else confused.

[DiceyPlay]

All the women are completely logical. Each woman asks another woman how many husbands they know of who are adulterers. Each woman replies 49. Every woman kills their spouse.

[Duke]

[ QUOTE ]
All the women are completely logical. Each woman asks another woman how many husbands they know of who are adulterers. Each woman replies 49. Every woman kills their spouse.

[/ QUOTE ]

You forgot step 4: a hot lesbian orgy with 51 participants. The Queen shows up.

~D

[dansalmo]

Hi Slickpoppa,

This is a really cool problem. I still have not seen an aswer in terms of when things happen. I think that it takes 50 days of no killings or everyone to conclude what must be done and then they all act simultaneously.

Is this the case?

[Rasputin]

[ QUOTE ]
I still have not seen an aswer in terms of when things happen.

[/ QUOTE ]

Go back and read the thread then.

[slogger]

On Day 50, assuming the queen's pronouncement occurred on Day 1. All 50 women would kill their husbands.

If only one man (not more) had been unfaithful, that man's wife would've known about it immediately upon hearing the queen's statement and killed him that day. This is because she would not have heard about any cheating husbands from another villager and, being perfectly logical, would deduce that her husband was the guilty party because if it was not her husband, she would have heard about it. The next day, all of the other women would know Wife 1 had killed her husband, and therefore, that their husbands had been faithful. They would know that the only way for the now-widow to have known her husband cheated would be if she had never heard of another man cheating.

Since there were 50 husbands that had cheated, the wives of those men would not immediately know that their husband had cheated because each would have heard of 49 acts of unfaithfulness. However, after 49 days had passed with no husband killing, each woman would now know that all 50 husbands had cheated and kill her husband.

[slogger]

[EDIT: What I say below is wrong - you are right - the queeen is necessary because each woman needs to know that each other woman knows that a certain number of men have been unfaithful before there can be any women who are able to prove after N days, that their husband cheated. I will leave up my misguided ramblings, as self-punishment /images/graemlins/blush.gif]

gm, this is not right.

See me response to Paul's earlier post above.

The queen's annoncement would only be news if it came on the same day that the 50th man finally took a mistress.

Otherwise, the "knowledge clock," as you so aptly put it, would already have been running.

Real Day 1 = the first day that there are no more faithful men in the village.

[TimmyMayes]

I think all men would die the day after the announcement....the original poster said all women know of the killings the instant they happen. When it is decreed that at least one man has been unfaithful you have a situation where everyone is waiting for someone to be killed THAT day as the law says but no one was now at 12:00:01 A chain reaction of killings occur leaving all men decimated.

Cheers,
Timothy

[gaming_mouse]

[ QUOTE ]
I think all men would die the day after the announcement....the original poster said all women know of the killings the instant they happen.

[/ QUOTE ]

You are right that "the instant they happen" makes things confusing. It raises the question of, How long do they wait before they interpret another woman's not killing her husband as the needed evidence about their own husband?

The question would be clearer if the law was: If a woman finds incontrovertible evidence that her husband has cheated, she will kill him at midnight. When a man is killed, all women are notified the following morning. Then the intended answer that everyone is killed on night 50 works.