Author |
Topic: 10 Prisoners and hats (Read 28704 times) |
|
Uwygoda
Newbie
Gender: 
Posts: 3
|
 |
Re: 10 Prisoners and hats
« Reply #25 on: Apr 9th, 2007, 12:07pm » |
 Quote  Modify
|
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_har d;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.
|
|
 IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 10 Prisoners and hats
« Reply #26 on: Apr 9th, 2007, 5:59pm » |
Quote Modify
|
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.
|
| « Last Edit: Apr 9th, 2007, 6:05pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
onlyme722
Newbie
Gender: 
Posts: 46
|
|
Re: 10 Prisoners and hats
« Reply #27 on: Feb 29th, 2008, 3:51pm » |
Quote Modify
|
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  .
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).
|
| « Last Edit: Feb 29th, 2008, 3:55pm by onlyme722 » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 10 Prisoners and hats
« Reply #28 on: Feb 29th, 2008, 7:58pm » |
Quote Modify
|
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. 
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
onlyme722
Newbie
Gender:
Posts: 46
|
|
Re: 10 Prisoners and hats
« Reply #29 on: Mar 4th, 2008, 10:12am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 10 Prisoners and hats
« Reply #30 on: Mar 4th, 2008, 10:27am » |
Quote Modify
|
on Mar 4th, 2008, 10:12am, 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: 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)
|
| « Last Edit: Mar 4th, 2008, 10:35am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
onlyme722
Newbie
Gender:
Posts: 46
|
|
Re: 10 Prisoners and hats
« Reply #31 on: Mar 4th, 2008, 10:52am » |
Quote Modify
|
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 (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%.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 10 Prisoners and hats
« Reply #32 on: Mar 4th, 2008, 11:11am » |
Quote Modify
|
on Mar 4th, 2008, 10:52am, onlyme722 wrote:| 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". |
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
onlyme722
Newbie
Gender:
Posts: 46
|
|
Re: 10 Prisoners and hats
« Reply #33 on: Mar 4th, 2008, 1:55pm » |
Quote Modify
|
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 )
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.
 #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 . 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 . I think my problem is that I really didn't sit down and try and work it out on paper , I should have, that helps me.
|
| « Last Edit: Mar 4th, 2008, 1:57pm by onlyme722 » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 10 Prisoners and hats
« Reply #34 on: Mar 4th, 2008, 2:32pm » |
Quote Modify
|
on Mar 4th, 2008, 1:55pm, 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 . 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 10 Prisoners and hats
« Reply #35 on: Mar 4th, 2008, 2:43pm » |
Quote Modify
|
What if the hats come in K (>2) different colours?
How many people can we safe then?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print