wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> 10 Prisoners and hats
        
(Message started by: irrational on Sep 19^th, 2006, 9:20am)

Title: 10 Prisoners and hats
Post by irrational on Sep 19^th, 2006, 9:20am

10 straight-jacketed prisoners are on death row. Tomorrow they will be arranged in single file, all facing one direction. The guy in the front of the line (he can't see anything in front of him) will be called the 1st guy, and the guy in the back of the line (he can see the heads of the other nine people) will be called the 10th guy. An executioner will then put a hat on everyone's head; the hat will either be black or white, totally random. Prisoners cannot see the color of their own hat. The executioner then goes to the 10th guy and asks him what color hat he is wearing; the prisoner can respond with either "black" or "white". If what he says matches the color of the hat he's wearing, he will live. Else, he dies. The executioner then proceeds to the 9th guy, and asks the same question, then asks the 8th guy ... this continues until all of the prisoners have been queried.

This is the night before the execution. The prisoners are allowed to get together to discuss a plan for maximizing the number of lives saved tomorrow. What is the optimal plan?

My apologies if this has already been posted.

Title: Re: 10 Prisoners and hats
Post by Barukh on Sep 19^th, 2006, 9:36am

This problem is on the riddles' page (http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#singleFileHatExec).

The links are here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1112716754;start=1#1[).

Title: Re: 10 Prisoners and hats
Post by alien on Sep 21^st, 2006, 1:08pm

It took me a week to solve this one on my own. :o And a headache. ;)

Title: Re: 10 Prisoners and hats
Post by rmsgrey on Sep 22^nd, 2006, 10:53am

So what happens when the guy at the back has a grudge against the 9th guy?

Title: Re: 10 Prisoners and hats
Post by Grimbal on Sep 25^th, 2006, 4:09am

Then he switches color.

Either that saves him and he can plead legitimate defense for killing his pal, or the switch kills him, in that case the bad guy gets killed by his own deeds. In both cases the story suits Hollywood moral standards.

Title: Re: 10 Prisoners and hats
Post by Icarus on Sep 25^th, 2006, 3:26pm

But what happens to everyone else?

Title: Re: 10 Prisoners and hats
Post by towr on Sep 26^th, 2006, 12:38am

on 09/25/06 at 15:26:49, Icarus wrote:

But what happens to everyone else?

I'd say the 9th guy dies, the rest lives.

Title: Re: 10 Prisoners and hats
Post by rmsgrey on Sep 26^th, 2006, 7:21am

on 09/26/06 at 00:38:35, towr wrote:

I'd say the 9th guy dies, the rest lives.

But what if the 9th guy doesn't trust the 10th guy?

Title: Re: 10 Prisoners and hats
Post by towr on Sep 26^th, 2006, 7:58am

on 09/26/06 at 07:21:19, rmsgrey wrote:

But what if the 9th guy doesn't trust the 10th guy?

Well, if no one trusts anyone, it's 50-50 chances allround.

Title: Re: 10 Prisoners and hats
Post by Grimbal on Sep 26^th, 2006, 7:59am

Yes, what if the 9th guy suspects the 10th guy would try something bad?

And What if the 7th guy trusts the 10th guy but believes the 9th guy is paranoid about the 10th, and feels the 8th guy is suicidal?

Title: Re: 10 Prisoners and hats
Post by rmsgrey on Sep 28^th, 2006, 5:39pm

My preferred version with prisoners is for the successes and failures to be announced during the process, and then N prisoners to be shot at random (where N is the number of wrong "guesses") - that way, every (non-suicidal) prisoner has an incentive to follow the system.

Suicidal prisoners are easier to accomodate under a scheme where only the prisoner(s) guessing wrong get(s) killed, but the correct colour of each hat is announced immediately after the guess - they can then self-terminate without taking anyone else with them.

In fact, if the correct colour is announced after each guess, then only the first prisoner to speak needs to be reliable when each controls their own fate, but lacks incentive; when the penalties/rewards are shared, then everyone has incentive, but any unreliable prisoner can mess things up.

My preferred formulation overall is for a gameshow, where a number of contestants play the game, the pot increases for each correct answer, and then all participants split the pot.

Title: Re: 10 Prisoners and hats
Post by grungy on Dec 9^th, 2006, 2:50am

If all the people are smart enough to understand this plan - it will even out to be a 95% success rate.

[hide]First of all, the guy at the back will see 9 hats. If he sees an odd amount of black hats, he will say black, if he sees an odd amount of white hats, he will say white. He is the only person who can die - and he has a 50% chance of survival anyway.

Then, say if the guy at the back says black, then it is the 9th person's turn. If he sees an odd number of black hats, he will know that his hat must be a white one. He will say white.

Then, the person ahead, knowing that since the other person said white, there must still be an odd number of black hats ahead. If the 8th person sees an even amount of black hats, he will know that his is white.

Then, this will continue all the way to the 1st person.[/hide]

Title: Re: 10 Prisoners and hats
Post by Whiskey Tango Foxtrot on Dec 9^th, 2006, 8:32am

If you notice the link in the second post, you'll see that this is indeed the answer. I'm curious, though. What can be done if there are 30 prisoners (to round it off) and 3 different hat colors? What if there are 40 prisoners and 4 different hat colors?

Title: Re: 10 Prisoners and hats
Post by Icarus on Dec 9^th, 2006, 9:49am

The first guy's chances get smaller, but everyone else can still be saved.

Title: Re: 10 Prisoners and hats
Post by Whiskey Tango Foxtrot on Dec 9^th, 2006, 10:13am

What would the process be for that? What would the first guy saying red, blue, or yellow mean?

Title: Re: 10 Prisoners and hats
Post by Icarus on Dec 9^th, 2006, 12:52pm

on 12/09/06 at 10:13:04, Whiskey Tango Foxtrot wrote:

What would the process be for that? What would the first guy saying red, blue, or yellow mean?

The 2-color riddle uses mod-2 logic...

Title: Re: 10 Prisoners and hats
Post by Uwygoda on Apr 7^th, 2007, 1:56pm

This riddle can be made much more interesting:

The basic problem stays the same, but this time there are an infinite (but enumerable) number of prisoners, and an infinite (but enumerable) number of hat colors. the solution assumes the Axiom of Choice (though non-mathematicians need not care about this fine point).

good luck to all.

anybody who wants the solution can email me.

Title: Re: 10 Prisoners and hats
Post by Icarus on Apr 7^th, 2007, 3:05pm

If we are limiting ourselves to denumerable sets, then there is no need for the Axiom of Choice, as the natural numbers are well-ordered even without it. It is only when you are dealing with larger sets that the A.C. is required.

Title: Re: 10 Prisoners and hats
Post by iyerkri on Apr 7^th, 2007, 10:29pm

on 12/09/06 at 09:49:32, Icarus wrote:

The first guy's chances get smaller, but everyone else can still be saved.

In the n-color riddle, I think n-1 prisoners' fate have to sacrificed to luck, in order to save the rest. Using mod-n logic will still leave doubts in the second guy's mind, if n > 2. But, he can trust luck and save the others.

Title: Re: 10 Prisoners and hats
Post by Uwygoda on Apr 7^th, 2007, 11:57pm

The solution I know to the denumerable version of the problem actually does require the A.C., even though natural numbers are well-ordered even without it.

If someone knows another solution which doesn't require it, I'd be glad to know.

Title: Re: 10 Prisoners and hats
Post by Barukh on Apr 8^th, 2007, 4:37am

on 04/07/07 at 23:57:40, Uwygoda wrote:

Maybe you will find this (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1112748623) relevant.

Title: Re: 10 Prisoners and hats
Post by Icarus on Apr 8^th, 2007, 5:21pm

Uwygoda is correct about it requiring the Axiom of Choice. I was too glib in my assessment (something I realized at the time, but didn't let it stop me). After all, while http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbn.gif can be well-ordered without the axiom of Choice, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/calp.gif(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbn.gif) cannot be (at least this is my understanding - if it could be, then you could construct unmeasurable sets without A.C., and I've heard that this is impossible).

I think that if you could make the needed choices here without A.C., you could also well-order http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbr.gif.

Barukh's link brings up a side question of interest to me: Was this puzzle Eigenray's invention, or did he also get it from someplace else? I am curious about this because I have seen certain other puzzles that were invented by members of this forum (Eric Yeh in particular) and first published here make their way around other venues, and even find their way back here as newer members repost them - unaware of their origin. "Gods of Gibberland" is a particular example.

Is this another one?

Title: Re: 10 Prisoners and hats
Post by Eigenray on Apr 8^th, 2007, 8:19pm

on 04/08/07 at 17:21:39, Icarus wrote:

Was this puzzle Eigenray's invention, or did he also get it from someplace else?

I heard it from someone else, and I don't think it was original with him (although he noticed the connection to [link=http://en.wikipedia.org/wiki/Diamond_principle_%28set_theory%29]diamond[/link] himself).

I hadn't considered the case of more than one hat color, but it looks like for any ordinality of prisoners, and any set of hat colors, the prisoners can still save all but the first.

Title: Re: 10 Prisoners and hats
Post by Icarus on Apr 8^th, 2007, 9:52pm

Yes. Deedlit's solution only needs minor modification to work for any number of hat colors. Specifically, if we can consider the hat colors to be values in some additive group G, then the first prisoner adds up the differences between the actual sequence and the representative sequence to obtain his value.

Title: Re: 10 Prisoners and hats
Post by Eigenray on Apr 8^th, 2007, 10:32pm

That's cleaner than what I was thinking (e.g., if there are infinitely many prisoners, and an infinite set of hats H, they would agree on a bijection of H with the set of all finite strings from H).

But if you just say that they can find a group of any given cardinality, then the strategy is independent of whether there are infinitely many prisoners or hats.

Title: Re: 10 Prisoners and hats
Post by Uwygoda on Apr 9^th, 2007, 12:07pm

First of all, as Barukh has pointed out, there's a whole forum about the infinite version of this riddle, at http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1112748623

anyways, in any solution to the infinite version you're required to choose representatives for an infinite number of equivalence classes (see for example the solution as it's posted at the other forum, and I'm guessing that any other solution is equivalent to it). but this is exactly the A.C. : being able to choose a member of any subgroup.

Title: Re: 10 Prisoners and hats
Post by Icarus on Apr 9^th, 2007, 5:59pm

It is a consequence of the Axiom of Choice, but it is not exactly the Axiom of Choice. After all, the sets that you are choosing from have a defined structure and a size limitation, while the Axiom of Choice holds for all sets of sets.

Title: Re: 10 Prisoners and hats
Post by onlyme722 on Feb 29^th, 2008, 3:51pm

I guess I'm going to sound like a complete idiot, but this may be due to my lack of mathematical understanding (beyond standard algebra). I have slightly grasped the concept of the AC but still fail to see how it pertains to this situation. Perhaps it is because you guys are rambling on about it and I need it explained in the fashion of "see spot run" to grasp the correlation here. If anyone can explain how something as random as this can be mathematically solved, please tell me, because until you do I don't understand how only half of the men can be guaranteed to live, whilst the others leave their fate to luck.

The immediate solution I came up with takes into consideration the fact that each individual knows the color of the hats of all men in front of him. If querying is to begin at the back of the line, I would suggest that #10 call out the color of #1, #9 declares the color of #2, and #6 the color of #3, and so on. Alas, only 1-5 will know for sure the color of their hat, so 6-10 have to hope their hat is the same color as their counterpart. All in all, a minimum of 50% saved, and as always the possibility of 100% being saved. I'd wager it would come to about 75%, considering that even though an individual may sacrifice themselves, they have a 50/50 chance, so "mathematically" the other half stand to lose 50% of their ranks (on average), so 75% saved is my overall guess (on a larger scale at least, considering you can't kill only half a man in this 10 man scenario)

I do know, however, that math isn't always this simple :P.

I realize this a very rudimentary solution, and will be fascinated to understand a more mathematical solution to the problem. However, the problem is that each man can only save ONE other man, and everything is randomized, so to me it would be like trying to determine each successive number in pi (considering no pattern was found last I checked).

Title: Re: 10 Prisoners and hats
Post by Icarus on Feb 29^th, 2008, 7:58pm

Not being familiar with the Axiom of Choice and the issues discussed here is hardly idiocy. Only severe Math wonks know or care about this stuff. Its just that there a lot of us here.

However, the Axiom of Choice, and most of the discussion in this thread, has little to do with the problem you are trying to solve. Rather, we were discussing an infinite version of the puzzle (i.e., an infinite number of prisoners, not just 10). Until you get the 10 prisoner version, you don't want to even consider the infinite one!

For the 10 prisoner version, no knowledge of advanced mathematics is needed. It is possible to definitely save 9 of the prisoners. There is nothing that can be done for the prisoner in the back. He has no information that can help him guess, so his chances can never be better than 50%. However, the other prisoners hear the answers of everyone behind them, and the prisoners can use this to their advantage. I'll not give you any more help than that here, to give you another chance to figure it out yourself. But if you get frustrated, then I suggest following the links. ;)

Title: Re: 10 Prisoners and hats
Post by onlyme722 on Mar 4^th, 2008, 10:12am

Icarus: At first I thought the same thing. That only the 10th has to be sacrificed. Here is the problem that I found:

For that theory the 10th guy must call out guy # 9's color...so let's say Guy #9 hears his color as just declared by #10 and he now knows that his hat is black, and he also knows that guy #8's hat is white. Guy #9 must now decide: save his own life and call out his own hat color (black), or tell guy #8 what his hat color is, and die. By declaring "my hat is white" #9 has just informed #8 that #8's color is white, but he has also doomed himself, because his hat is actually Black. Therein, each prisoner can ONLY save the person in front of them, but if this were carried out infinitely, only #1 would be GUARANTEED to live, every one else will only live if they are lucky enough to have the same color hat of the person in front of them.

I do not see how the solution you just presented to me works in any fashion at all. Unless, of course, you say that each prisoner is allowed to both tell the guy in front of him of their hat color AND declare his own. However, the question only states that they are merely allowed to "guess" the color of their hat.

Therefore, I still think (in my own logic, of course) that My solution makes the most sense to me...it guarantees a minimum of 50% saved, all the way up to an average of 75% on a larger (infinite?) scale. The only problem with the infinite version is you begin to to consider logistics such as: "Well, how could people at the back see the colors of the hats of the people at the front of an infinitely outstretching line of prisoners?" But that is only a problem in the actual practice of the solution, not its theory on paper.

Therefore, I once again suggest that 10 declare #1's hat, 9 declare number 2, 8 declare #3 and so on. 1-5 live, 6-10 need to depend on luck and odds.

Title: Re: 10 Prisoners and hats
Post by towr on Mar 4^th, 2008, 10:27am

on 03/04/08 at 10:12:39, onlyme722 wrote:

Icarus: At first I thought the same thing. That only the 10th has to be sacrificed. Here is the problem that I found:

For that theory the 10th guy must call out guy # 9's color...
<snip>

Well, yeah, that theory is bunk. But that doesn't mean 10 can't call out something else that is sufficiently informative to 9.
Note that 9 can see 1..8 as well as hear what 10 calls out; 8 can see 1..7 as well as hear 10 and 9 call out; etc.

Let me add one clue: [hide]What 10 says is interpreted to be a statement about all the people he sees. (In a way that they agreed on the day before, as allowed)[/hide]

Title: Re: 10 Prisoners and hats
Post by onlyme722 on Mar 4^th, 2008, 10:52am

Towr: I see what you are saying. I believe that you are suggesting what I have already seen suggested. That 10 call out the color that has the most distinct odds, or that the color he calls out correlates to a previously defined set of odds. As someone else said "10 sees an odd amount of black hats".

There is still a problem. Any such declaration would still be a very obscure "guestimation". Each person would still merely be depending on luck. However, any method that tells an individual resolutely of their hat color would be much preferred. In other words, I would much rather hear what my hat color IS than to be told that "there are more black hats than white as far as I can see". This method would require only a base generalization, and would not be able to lend itself distinctly to the saving of any particular person. All it really succeeds in doing is alerting the guesser to their odds of being correct, but ultimately, each is left only to GUESS their hat's color based on what they believe their odds to be. This is surely more dependable than no system at all, but it is hardly a system that guarantees ANY particular individual to live.

To me this really is no help, but I will let it stew in my brain and try think along this new avenue of thought and see if I can think of any example wherein this theory might be successfully executed.

So in conclusion. No one has yet to convince me that my theory isn't the best I've heard so far :P (I don't mean to sound cocky). My solution GUARANTEES 50% saved, but when the odds are also taken into play, it can save around 75%.

Title: Re: 10 Prisoners and hats
Post by towr on Mar 4^th, 2008, 11:11am

on 03/04/08 at 10:52:03, onlyme722 wrote:

If 10 calls out which colour hat he sees an odd number of, then everyone has enough information to figure out their own hat colour.

If 10 calls out black, then 9 knows that that if he sees an even number of black hats, his must be black as well, because otherwise 10 wouldn't see an odd number of them.
8 then knows what hat 9 had, and whether excluding 9 ten saw an odd or even number of black hats, and thus she'll know her hat colour as well; etc.

Title: Re: 10 Prisoners and hats
Post by onlyme722 on Mar 4^th, 2008, 1:55pm

Yes I do see what you are saying. I definitely see the logic in where you are coming from, I have suddenly had that "Ahhhhh" moment. I realized that I need to work it out on paper, so I started to do so.

1)I jotted down just a random order or 10 B's and W's. This was the sequence: BWWBWBBWWB, so this gives us 5 w's and 5 b's (i think this is my subconscious expression for a desire for things to be even and symmetrical :P)
2)Since 10 is the only person who will never ever be saved, we rule him out.
3)So there are 9 more hats in play that can be "solved".
4)#10 sees 4 b's and 5 w's, so he declares WHITE because 5 is the odd number,(#10's hat is black, btw)
5)#9 sees 4 blacks and 4 whites, so he knows his hat must be white for this rule to be true.
6)#8 is now aware of 4 whites, and 4 blacks, so once again he knows his hat must be WHITE as well.
7)#7 is now aware of 5 whites, and 3 blacks. He knows that if he were to guess WHITE that would have meant 10 saw an even number of whites, which is not what 10 declared, so his hat must be BLACK.
8)#6 is now aware of 4 whites, 4 blacks so once again, he guesses WHITE.
9)#5 is now aware of 5 whites, 3 blacks, and same as #7, he guesses BLACK.
10)#4 does the same.
11)#3 sees it how 6 did, #2 is well
12)#1 sees it how all other black hats did.

OK so after finally putting this idea into action, it makes sense to me! YAY! I've tried 2 different scenarios, and it stays true. There will always be an odd number in the 10 men scenario, or in any number of men that totals to an even amount. However, put 11(or any odd number)men in a row and put 6 white hats and 5 black hits, #11 will see an even number of whites and blacks :P. What would he do then?

OH well, thank you so much for being patient and helping me to get it, I really was just trying to grasp the concept :P. I think my problem is that I really didn't sit down and try and work it out on paper :P, I should have, that helps me.

Title: Re: 10 Prisoners and hats
Post by towr on Mar 4^th, 2008, 2:32pm

on 03/04/08 at 13:55:20, onlyme722 wrote:

There will always be an odd number in the 10 men scenario, or in any number of men that totals to an even amount. However, put 11(or any odd number)men in a row and put 6 white hats and 5 black hits, #11 will see an even number of whites and blacks :P. What would he do then?

Well, they could just agree that when the man at the back says "white" it means that there's an odd number of white hats, and that when he says "black" that it means there's an even number of white hats.

Title: Re: 10 Prisoners and hats
Post by towr on Mar 4^th, 2008, 2:43pm

What if the hats come in K (>2) different colours?
How many people can we safe then?