Harder Interview Question #2

slickpoppa · #1 02-02-2005, 03:37 AM

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 · #2 02-02-2005, 07:24 AM

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 · #3 02-02-2005, 07:34 AM

[ 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 · #4 02-02-2005, 11:16 AM

[ 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 · #5 02-02-2005, 11:29 AM

all men are killed.

slickpoppa · #6 02-02-2005, 11:32 AM

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

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 · #8 02-02-2005, 02:38 PM

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

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

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