bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

Schik's got it; 7/8 is correct.

It shouldn't be that hard to see that 7/8 is the best possible; after all, if you run the problem over all 128 hat possibilities, then the prisoners' strategy will always give the same number of correct answers as wrong answers. Since they need at least one correct answer to live and can have at most seven incorrect answers to die, they can live at most seven times as often as they die.

An easier way to see the strategy is the following: number the prisoners 1 through 7. Consider the binary representations of the numbers of all people with red hats and XOR them together. This is going to be zero 1/8 of the time, so have all the prisoners assume it isn't zero and deduce their own color accordingly (if possible, otherwise they write nothing.) If the XOR sum actually isn't zero, exactly one person will guess and guess correctly; if it is zero, they'll all guess incorrectly.

[Edited by bibelot on 01-02-2004 at 06:44 PM GMT]

agaricus5
Level: Smitemaster
Rank Points: 1838
Registered: 02-04-2003
IP: Logged

bibelot wrote:
An easier way to see the strategy is the following: number the prisoners 1 through 7. Consider the binary representations of the numbers of all people with red hats and XOR them together. This is going to be zero 1/8 of the time, so have all the prisoners assume it isn't zero and deduce their own color accordingly (if possible, otherwise they write nothing.) If the XOR sum actually isn't zero, exactly one person will guess and guess correctly; if it is zero, they'll all guess incorrectly.

Huh?

Wait!

You said this:

There are seven men taken prisoner, destined for execution. The executioner, being of a kind sort with a penchant for hats, proposes the following:

On the day of the execution, the seven men will be put in a circle and a hat will be placed on each man's head, either red or white, with equal probability. They will each then be given a piece of paper and a pencil. On the paper, they are to write what they believe is the color of their hat, either "red", "white", or they may leave it blank. The men will be set free if nobody guesses the wrong color on their paper and at least one person guesses correctly; they are all executed otherwise. (It is assumed that there will be no cheating, or else they will also be executed.) The men plan their strategy the night before. What is their best strategy, and what is the chance that they will survive?

I thought this means all the men die if any of them guess wrongly.

____________________________
Resident Medic/Mycologist

bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

Here, I'll give an example or two.

Suppose person 2, 3, and 5 have red hats. If we XOR them we get 4. So person 4 thinks, "If I have a red hat, then the total XOR of the red hatted people is 0, so I'll say I have a white hat," and he writes white. But, say, person 1 thinks, "If I have a red hat, the total XOR is 5, but if I have a white hat, it's 4, so I can't guess what color my hat is," and leaves the paper blank. Likewise, all the people besides person 4 will not guess, and the prisoners will win.

Suppose person 3, 5, and 6 have red hats. Their XOR is 0. Then person 1 will think, "If I have a white hat, the total red XOR will be 0, so I'll say I have a red hat," while person 3 will think, "If I have a red hat, the total red XOR will be 0, so I'll say I have a white hat." Likewise, all the prisoners will guess incorrectly, and the prisoners will lose, by a lot.

[Edited by bibelot on 01-02-2004 at 06:58 PM GMT]

Oneiromancer
Level: Legendary Smitemaster

Rank Points: 2936
Registered: 03-29-2003
IP: Logged

But agaricus has a good point, the original puzzle implies all or nothing as far as I can see too. How do you address this concern?

Edit: never mind, the puzzle is to find the chance of them all surviving, not the number who survive. That's what was found, all is happy.

Game on,

[Edited by Oneiromancer on 01-02-2004 at 07:29 PM GMT: Duh]

____________________________
"He who is certain he knows the ending of things when he is only beginning them is either extremely wise or extremely foolish; no matter which is true, he is certainly an unhappy man, for he has put a knife in the heart of wonder." -- Tad Williams

agaricus5
Level: Smitemaster
Rank Points: 1838
Registered: 02-04-2003
IP: Logged

OK. I don't want to argue, but this use of logic XOR is really confusing me. How do you use it on 7 people all at once? Is there a clearer way to explain it, for I can't understand you.

[Edited by agaricus5 on 01-02-2004 at 07:46 PM GMT]

____________________________
Resident Medic/Mycologist

bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

It's the same as doing XOR between two things multiple times. Another way of saying it is to write down the numbers in binary, and if a given column has an odd number of 1's, the XOR sum has a 1 in that column, otherwise it has a 0. So, if we sum 3, 5, and 7, we write:

011
101
111

and only the one's column has an odd number of one's so the XOR sum is 1.

agaricus5
Level: Smitemaster
Rank Points: 1838
Registered: 02-04-2003
IP: Logged

bibelot wrote:
It's the same as doing XOR between two things multiple times. Another way of saying it is to write down the numbers in binary, and if a given column has an odd number of 1's, the XOR sum has a 1 in that column, otherwise it has a 0. So, if we sum 3, 5, and 7, we write:

011
101
111

and only the one's column has an odd number of one's so the XOR sum is 1.

Ah, I see. Didn't know that. Thanks!

____________________________
Resident Medic/Mycologist

Schik
Level: Legendary Smitemaster

Rank Points: 5453
Registered: 02-04-2003
IP: Logged

Okay, I guess it's my turn. The whole xor thing reminds me of a good one.

Most of us have probably heard the one about two guys standing at a fork in the road, one of whom tells the truth and the other who lies. Here's a bit of a twist on that one:

Erik, Mike, and Gerry are all sitting in a room. You've never met any of them, nor do you know of any way to identify any of them using any of your senses. Erik always tells the truth. Mike always lies. Gerry always answers the XOR of what Erik and Mike would say to the same question.
Just to be clear - If Erik and Mike would answer the same, then Gerry would answer in the negative, and if Erik and Mike would answer differently, then Gerry would answer in the positive.
Okay. Back to the puzzle. These three speak a language unknown to you. You know that they have single words that mean "Yes" and "No", but you don't know what these words are.

Your task is to determine who is who by asking three questions. Each question is asked to one person. You may ask the same question to multiple people, but then it counts as multiple questions. You can ask one person multiple questions - again, counting as multiple questions.

They understand English, but will only answer in their own language. They will only answer Yes/No questions, and will respond with the single word meaning either "Yes" or "No" in their language.

Since this might be a little confusing, here's a quick example:

Say you ask person A "Are you Erik?" If A is Erik, he would truthfully respond in the positive. If A is Mike, he would lie, and respond in the positive. If A is Gerry, he would respond positive XOR positive, which would be be negative.

I hope I've made the rules clear. Feel free to ask for further explanation if anything's not clear.


____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

Mattcrampy
Level: Smitemaster

Rank Points: 2388
Registered: 05-29-2003
IP: Logged

Well, I've seen a picture of Erik, so I should be able to pick him out, but they do indeed speak a language unknown to me. PHP.

But wait, what if he's wearing a Mike mask and Mike's wearing and Erik mask? Then I'm trapped in MI:2! Gawds.

Hmm, well let's ask someone if they're Gerry. If they answer yes, it's Mike, in which case ask someone if they're Erik. If no, ask the same person if they're Erik. They will answer truthfully in both cases.

If we know Mike and Erik or Gerry, we're done. If we don't know who Mike is, and we have Erik, ask one if they're Mike (Mike answers now, Gerry yes), and if we have Gerry, ask one if they're Gerry (Erik says no, Mike says yes).

Matt

____________________________
What do you call an elephant at the North Pole?

Schik
Level: Legendary Smitemaster

Rank Points: 5453
Registered: 02-04-2003
IP: Logged

Mattcrampy wrote:
Hmm, well let's ask someone if they're Gerry. If they answer yes, it's Mike, in which case ask someone if they're Erik.

Actually, both Gerry and Mike would say Yes. But most importantly, you don't know what the words for Yes and No are, so you don't know anything at this point.



____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

agaricus5
Level: Smitemaster
Rank Points: 1838
Registered: 02-04-2003
IP: Logged

Schik wrote:

Mattcrampy wrote:
Hmm, well let's ask someone if they're Gerry. If they answer yes, it's Mike, in which case ask someone if they're Erik.

Actually, both Gerry and Mike would say Yes. But most importantly, you don't know what the words for Yes and No are, so you don't know anything at this point.

So you could ask for Erik first then. Erik and Mike would both say a word, while Gerry would say something else. The word spoken twice is "yes", for Erik will tell the truth and Mike will lie, and the word spoken once would be "no", as the others said something else. The person who said "no" would then be Gerry, for he answers the XOR of the others. Now ask for Gerry. Erik will say "no", and Mike will lie and say "yes".

[Edited by agaricus5 on 01-02-2004 at 09:09 PM GMT]

____________________________
Resident Medic/Mycologist

Schik
Level: Legendary Smitemaster

Rank Points: 5453
Registered: 02-04-2003
IP: Logged

agaricus5 wrote:
So you could ask for Erik first then. Erik and Mike would both say a word, while Gerry would say something else. The word spoken twice is yes, for Erik will tell the truth and Mike will lie, and the word spoken once would be no, as the others said the same thing. The person who said no would then be Gerry. Now ask for Gerry. Erik will say no, and Mike will lie and say yes.

You've asked too many questions then. You get three questions, and they're each aimed at one person. After your first round of asking everyone if they are Erik, you're done with all three questions.


____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

Oneiromancer
Level: Legendary Smitemaster

Rank Points: 2936
Registered: 03-29-2003
IP: Logged

Schik wrote:
Erik, Mike, and Gerry are all sitting in a room. You've never met any of them, nor do you know of any way to identify any of them using any of your senses.

Mattcrampy wrote:
Well, I've seen a picture of Erik, so I should be able to pick him out, but...

I'm pretty sure your whole sentence was probably just a joke, but this still makes me assume that you haven't read the problem carefully enough. Just my first impression.

Game on,


____________________________
"He who is certain he knows the ending of things when he is only beginning them is either extremely wise or extremely foolish; no matter which is true, he is certainly an unhappy man, for he has put a knife in the heart of wonder." -- Tad Williams

Schik
Level: Legendary Smitemaster

Rank Points: 5453
Registered: 02-04-2003
IP: Logged

Oneiromancer wrote:

Schik wrote:
Erik, Mike, and Gerry are all sitting in a room. You've never met any of them, nor do you know of any way to identify any of them using any of your senses.

Mattcrampy wrote:
Well, I've seen a picture of Erik, so I should be able to pick him out, but...

I'm pretty sure your whole sentence was probably just a joke, but this still makes me assume that you haven't read the problem carefully enough. Just my first impression.

Not to mention that I never gave any last names... it's pure coincidence that those are the first names of three DROD developers.

____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

Watcher
Level: Smitemaster

Rank Points: 902
Registered: 02-04-2003
IP: Logged

Schik wrote:
Erik, Mike, and Gerry are all sitting in a room. You've never met any of them, nor do you know of any way to identify any of them using any of your senses. Erik always tells the truth. Mike always lies. Gerry always answers the XOR of what Erik and Mike would say to the same question.
Just to be clear - If Erik and Mike would answer the same, then Gerry would answer in the negative, and if Erik and Mike would answer differently, then Gerry would answer in the positive.
Okay. Back to the puzzle. These three speak a language unknown to you. You know that they have single words that mean "Yes" and "No", but you don't know what these words are.

Your task is to determine who is who by asking three questions. [...] They understand English, but will only answer in their own language. They will only answer Yes/No questions, and will respond with the single word meaning either "Yes" or "No" in their language.

It cannot be done.

Here's the proof: Since Gerry's answer always can be determined from Erik and Mike's, there are basically four kinds of questions:

1. Erik and Mike answers Yes, Gerry answers No. For example, "Are you Erik?".
2. All three answer No. For example, "Are you Mike?"
3. Mike and Gerry answers Yes, Erik answers No. For example, "Are you Gerry?".
4. Erik and Gerry answers Yes, Mike answers No. For example, "Are you either Erik or Mike?".

If you ask a question of type 2, you'll know what the words mean. But this gives you no information about who's who. Then, you only have two Yes/No questions left, and that isn't enough to distinguish between six possibilities.

Therefore you can't ask type 2 questions. Now, if you ask two different people two different types of questions, you learn nothing about the meaning of the words, nor do you learn enough about who the two people are. (For example, ask someone a type 1 question, then someone else a type 3 question. Whatever the answers given are, Mike may be any of the three people.)

Therefore, you'll either ask the same person twice, or the same type of question twice. If you ask the same person twice, and he gives you two different answers, you do not know what the words mean, and there's two possibilities for the identity of the person you asked, and three for both of the others. If you ask the same typ of question twice, and get two different answers, again, you do not know what the words mean, and there's two possibilities for the identity of the person you did not talk to, and three for both of the others.

Therefore, the puzzle is unsolvable.

____________________________
Today the refrigerator, tomorrow the world!

Skylancer64
Level: Delver
Rank Points: 62
Registered: 10-25-2003
IP: Logged

Darn. I figured out a way to conclusively determine who is who, but 1/3 of the time, I'll take me 3 questions, and 2/3 of the time it'll take 4 questions. (Depending on the person I happen to be asking a certain question, it varies)

Edit - Hey, you slipped in a post under me!

[Edited by Skylancer64 on 01-02-2004 at 10:09 PM GMT]

____________________________
Complexity is the source of Life.

Schik
Level: Legendary Smitemaster

Rank Points: 5453
Registered: 02-04-2003
IP: Logged

Watcher wrote:
Therefore, the puzzle is unsolvable.

Sorry, that's not correct. There is definitely a solution. After a bit of time, I might start dropping some clues.

____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

Watcher
Level: Smitemaster

Rank Points: 902
Registered: 02-04-2003
IP: Logged

Schik wrote:

Watcher wrote:
Therefore, the puzzle is unsolvable.

Sorry, that's not correct. There is definitely a solution. After a bit of time, I might start dropping some clues.

Could you PM me with the solution? Because at the moment I'm quite convinced that it can't exist, so I've pretty much given up looking for one. I won't talk about it if you're correct, of course.

____________________________
Today the refrigerator, tomorrow the world!

DiMono
Level: Smitemaster

Rank Points: 1181
Registered: 09-13-2003
IP: Logged

Ask the first two people if the third is Gerry. If the third is Gerry, Erik will say yes and Mike will say no. If it's not Gerry, Erik would say no, Mike would say yes, and Gerry would say yes. If you get two answers that are the same, you know the third person is Erik, and have yes identified. If you get two answers that are different, the third person is not Erik.

If Erik is identified, you simply ask him if Mike would say one of the other two is Mike. Knowing Mike would say he's not Mike and Gerry is, if Erik says no then the person you were referring to is Mike, otherwise it's Gerry.

If Erik's not identified, you need a question that discerns Erik from the first two, and identifies the third. I can't think of such a question yet, hopefully someone else can and will run with it.

____________________________
Deploy the... I think it's a yellow button... it's usually flashing... it makes the engines go... WHOOSH!

Watcher
Level: Smitemaster

Rank Points: 902
Registered: 02-04-2003
IP: Logged

DiMono wrote:
If Erik's not identified, you need a question that discerns Erik from the first two, and identifies the third. I can't think of such a question yet, hopefully someone else can and will run with it.

Precisely the problem I ran into. Such a question can't exist, because you can only get two different answers, but there's four possibilities left.

____________________________
Today the refrigerator, tomorrow the world!

The_Red_Hawk
Level: Smitemaster
Rank Points: 783
Registered: 09-02-2003
IP: Logged

Schik - just for clarification, you said that Erik, Mike, and Gerry will answer in their own language. Do they all speak the same language, or do they each have different ones?

____________________________
Slashing, whirling, diving, twirling,
Snapping, turning, rising, swirling,
Screeching, flipping, gliding, sliding,
The red hawk's dance of death.

.....the king of the skies.....

Schik
Level: Legendary Smitemaster

Rank Points: 5453
Registered: 02-04-2003
IP: Logged

The_Red_Hawk wrote:
Schik - just for clarification, you said that Erik, Mike, and Gerry will answer in their own language. Do they all speak the same language, or do they each have different ones?

They all speak the same language, which uses the same alphabet as English, but the words are not related to their English counterparts at all.

And no, you can't steal their wallets to look at their drivers licenses.

____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

DiMono
Level: Smitemaster

Rank Points: 1181
Registered: 09-13-2003
IP: Logged

Best I can get so far is 2/3 accuracy

Am I on the right track?

[Edited by DiMono on 01-02-2004 at 11:27 PM GMT]

____________________________
Deploy the... I think it's a yellow button... it's usually flashing... it makes the engines go... WHOOSH!

The_Red_Hawk
Level: Smitemaster
Rank Points: 783
Registered: 09-02-2003
IP: Logged

"If I ask the other two if they are [their correct name], what would they say?"

If he's Erik, he'll say "Mike will say no and Gerry will say yes."
If he's Mike, he'll say "Erik will say no and Gerry will say no."
If he's Gerry, he'll say "Erik will say yes and Mike will say yes."

I ask this of two of them. The guy with different answers is Erik, if I pick him. The others, if I pick them, have same answers. Now all I need is a question to determine which answer is yes and which is no. If I do, it is easy to figure out who is who.

I then ask Erik (who can be discovered from the previous two questions) if two plus two is four. Then I know what "yes" is and can find out everybody.

[Edited by The_Red_Hawk on 01-03-2004 at 12:12 AM GMT]

____________________________
Slashing, whirling, diving, twirling,
Snapping, turning, rising, swirling,
Screeching, flipping, gliding, sliding,
The red hawk's dance of death.

.....the king of the skies.....

Watcher
Level: Smitemaster

Rank Points: 902
Registered: 02-04-2003
IP: Logged

The_Red_Hawk wrote:
"If I ask the other two if they are [their correct name], what would they say?"

If he's Erik, he'll say "Mike will say no and Gerry will say yes."
If he's Mike, he'll say "Erik will say no and Gerry will say no."
If he's Gerry, he'll say "Erik will say yes and Mike will say yes."

But they will only answer yes/no questions. You can't get complicated answers like these.

____________________________
Today the refrigerator, tomorrow the world!

Avon
Level: Delver
Rank Points: 47
Registered: 12-06-2003
IP: Logged

The_Red_Hawk wrote:
"If I ask the other two if they are [their correct name], what would they say?"

They only answer Yes/No questions.

I guess I spent too long writing that.

[Edited by Avon on 01-03-2004 at 12:19 AM GMT]

____________________________
"Les hommes ne sont jamais plus ingénieux que dans l'invention des jeux." -- Gottfried Wilhelm Leibniz

Oneiromancer
Level: Legendary Smitemaster

Rank Points: 2936
Registered: 03-29-2003
IP: Logged

Actually, here's something I am confused about. Let's say you point to Erik and ask Gerry "Is he Mike?" How does Gerry interpret this? Is it like going up to each person and asking "Are you Mike?", in which case the answers would be No/No/No for Erik/Mike/Gerry, respectively, or is it like going up to each person and pointing to Erik and asking "Is he Mike?", which would give the answers No/Yes/Yes, assuming when you ask Erik you have to point to Erik. The problem is whether Gerry can really determine the correct question to answer in an XOR manner if it becomes impossible to ask the same question of all three people.

As an aside, asking "Are you Mike?" was part of my initial strategy since you learn what "No" means but I'm not sure if it's viable yet.

Game on,

____________________________
"He who is certain he knows the ending of things when he is only beginning them is either extremely wise or extremely foolish; no matter which is true, he is certainly an unhappy man, for he has put a knife in the heart of wonder." -- Tad Williams

mrimer
Level: Legendary Smitemaster

Rank Points: 5197
Registered: 02-04-2003
IP: Logged

bibelot wrote:
...if a given column has an odd number of 1's, the XOR sum has a 1 in that column, otherwise it has a 0...

Just for the record, I think the correct term for "multiple XOR" is parity. For example, an error-checking "parity bit" is set to 1 if there's an odd number of 1 bits in the number, else it's 0.

...hmm...I hope you all understand that I wrote this before I started reading about Matt's riddle

[Edited by mrimer on 01-03-2004 at 12:41 AM GMT: once I realized I was a liar]

____________________________
Gandalf? Yes... That's what they used to call me.
Gandalf the Grey. That was my name.
I am Gandalf the White.
And I come back to you now at the turn of the tide.

Scott
Level: Smitemaster
Rank Points: 578
Registered: 02-12-2003
IP: Logged

Red hawks answer looks like it works to me but then I am not the one that needs to decide. I'm not sure I understand what you mean about Gerry not being able to determine the question Oneiro.

The_Red_Hawk
Level: Smitemaster
Rank Points: 783
Registered: 09-02-2003
IP: Logged

My answer isn't right because they can only answer yes/no questions.

____________________________
Slashing, whirling, diving, twirling,
Snapping, turning, rising, swirling,
Screeching, flipping, gliding, sliding,
The red hawk's dance of death.

.....the king of the skies.....