Harder Interview Question #2 - Page 2

Rasputin · #11 02-02-2005, 03:47 PM

[ 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 · #12 02-02-2005, 04:58 PM

[ 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 · #13 02-02-2005, 07:26 PM

[ 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 · #14 02-02-2005, 08:13 PM

What is the point of the queen?

Every woman already knows that at least 1 person cheated.

gaming_mouse · #15 02-02-2005, 08:34 PM

[ 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 · #16 02-02-2005, 08:47 PM

[ 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 · #17 02-02-2005, 08:54 PM

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 · #18 02-02-2005, 08:59 PM

[ 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 · #19 02-02-2005, 09:05 PM

[ 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 · #20 02-02-2005, 10:19 PM

[ 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