Prisoners with hats
-
I had the following problem posed to me while on holiday a couple of weeks ago. a sadistic dictator(aren't they all) has 100 political prisoners. In lieu of plain execution he decides to pose them a problem so that some of them can escape if they are smart enough. At random each of them will have a hat placed on his head. This hat may be red green or blue and no prisoner knows what colour his own hat is. The prisoners will all be stood in a line facing the same way so that each can see all the people in the line infront of him. Starting at the back of the line the guards will ask each prisoner in turn what colour his hat is with death being the punishment for an incorrect answer. Each prisoner will have heard the answer given by the man behind him and the result of that answer. The prisoners are given time to discuss between them a strategy for saving themselves. How many prisoners can you save? An example of a rubbish strategy might be: if the guy behind gets executed you repeat what he said if the guy behind lives you say the colour of the guy infront of you's hat first guy says the guy in front's hat That should save at least half of the prisoners Russell PS i believe the guy who posed this question to me found it on tinterweb so no googling for spoilers.
Easy, we can ensure that N-1 will live and a chance of 50% for the last one to live. The strategy is for the last one he will try to make the even odd, like if he sees 40 red hats, and 59 blue ones, then he chooses blue to make it even, hence he has a chance of a 50-50 , then the one infornt of him will see the 98 hats and then will realize that if they are (the 98) even and even, (also that will depend on if the guy behind killed or not, he will know that that color said by the man before is the same as his color.: And so on. -D
-
I had the following problem posed to me while on holiday a couple of weeks ago. a sadistic dictator(aren't they all) has 100 political prisoners. In lieu of plain execution he decides to pose them a problem so that some of them can escape if they are smart enough. At random each of them will have a hat placed on his head. This hat may be red green or blue and no prisoner knows what colour his own hat is. The prisoners will all be stood in a line facing the same way so that each can see all the people in the line infront of him. Starting at the back of the line the guards will ask each prisoner in turn what colour his hat is with death being the punishment for an incorrect answer. Each prisoner will have heard the answer given by the man behind him and the result of that answer. The prisoners are given time to discuss between them a strategy for saving themselves. How many prisoners can you save? An example of a rubbish strategy might be: if the guy behind gets executed you repeat what he said if the guy behind lives you say the colour of the guy infront of you's hat first guy says the guy in front's hat That should save at least half of the prisoners Russell PS i believe the guy who posed this question to me found it on tinterweb so no googling for spoilers.
Russell Jones wrote:
At random each of them will have a hat placed on his head. This hat may be red green or blue and no prisoner knows what colour his own hat is.
If the choice of hats is truly random, then there is no relationship between the hat color of one prisoner and that of another. The odds of any prisoner having any particular hat color is 1 in 3. Knowing the hat colors of all those in front of you is not useful (in fact it is not useful to know all the other hat colors, since any color you guess for your own hat still has a 2 in 3 chance of being wrong.) any strategy will have the same result: 1/3 will survive, since they have a 1 in three chance that their guess will be right.
-
I had the following problem posed to me while on holiday a couple of weeks ago. a sadistic dictator(aren't they all) has 100 political prisoners. In lieu of plain execution he decides to pose them a problem so that some of them can escape if they are smart enough. At random each of them will have a hat placed on his head. This hat may be red green or blue and no prisoner knows what colour his own hat is. The prisoners will all be stood in a line facing the same way so that each can see all the people in the line infront of him. Starting at the back of the line the guards will ask each prisoner in turn what colour his hat is with death being the punishment for an incorrect answer. Each prisoner will have heard the answer given by the man behind him and the result of that answer. The prisoners are given time to discuss between them a strategy for saving themselves. How many prisoners can you save? An example of a rubbish strategy might be: if the guy behind gets executed you repeat what he said if the guy behind lives you say the colour of the guy infront of you's hat first guy says the guy in front's hat That should save at least half of the prisoners Russell PS i believe the guy who posed this question to me found it on tinterweb so no googling for spoilers.
The first prisoner calls out the color of the most common hat color. Now assuming that the first prisoner is not one of the five that are possible color bind (according to Roger Stoltz based on the continual use of the 'his'). This would save from 1/3 to the maximum number of occurrence of the most common hat color. If for chance the first prisoner is color blind this would be know by the prisoners as a revelation during the strategy development period. So in that case the maximum loss of prisoners is 1/3 or maximum number of occurrence of the most common hat color -n. "n" being the number of color blind prisoners in sequence at the beginning of the line.
God Bless, Jason
DavidCrow wrote:
It would not affect me or my family one iota. My wife and I are in charge of when the tv is on, and what it displays. I do not need any external input for that.
-
The instruction says that the prisoners doesn't know the colour of their own hat at the beginning of the test. Since the instructions doesn't clearly state that the prisoners aren't allowed to take their hats off and look at them, this is my suggestion. At this point it would seem like it should be possible to save 100% of the prisoners, but this would be an incorrect assumption: 5% of the male population are colour blind. If the prisoners may be of female sex, then it would be possible to save 97.5% of them considering that there are two sexes and statistically 50% of the prisoners may be female. Colour blindness cannot affect women, they can be a genetic carrier but their sight won't be affected. :-D
"It's supposed to be hard, otherwise anybody could do it!" - selfquote
"High speed never compensates for wrong direction!" - unknownRoger Stoltz wrote:
Colour blindness cannot affect women, they can be a genetic carrier but their sight won't be affected.
That's incorrect. Colorblindness is due to a defect on the X chromosome and is much more common among men as a result, but the daughter of a colorblind man and a woman carrier has a 50% chance of being colorblind by inheriting the defect from both parents.
-- You have to explain to them [VB coders] what you mean by "typed". their first response is likely to be something like, "Of course my code is typed. Do you think i magically project it onto the screen with the power of my mind?" --- John Simmons / outlaw programmer
-
The instruction says that the prisoners doesn't know the colour of their own hat at the beginning of the test. Since the instructions doesn't clearly state that the prisoners aren't allowed to take their hats off and look at them, this is my suggestion. At this point it would seem like it should be possible to save 100% of the prisoners, but this would be an incorrect assumption: 5% of the male population are colour blind. If the prisoners may be of female sex, then it would be possible to save 97.5% of them considering that there are two sexes and statistically 50% of the prisoners may be female. Colour blindness cannot affect women, they can be a genetic carrier but their sight won't be affected. :-D
"It's supposed to be hard, otherwise anybody could do it!" - selfquote
"High speed never compensates for wrong direction!" - unknownRoger Stoltz wrote:
Colour blindness cannot affect women, they can be a genetic carrier but their sight won't be affected.
See here for a different take.
"A good athlete is the result of a good and worthy opponent." - David Crow
"To have a respect for ourselves guides our morals; to have deference for others governs our manners." - Laurence Sterne
-
Easy, we can ensure that N-1 will live and a chance of 50% for the last one to live. The strategy is for the last one he will try to make the even odd, like if he sees 40 red hats, and 59 blue ones, then he chooses blue to make it even, hence he has a chance of a 50-50 , then the one infornt of him will see the 98 hats and then will realize that if they are (the 98) even and even, (also that will depend on if the guy behind killed or not, he will know that that color said by the man before is the same as his color.: And so on. -D
-
I had the following problem posed to me while on holiday a couple of weeks ago. a sadistic dictator(aren't they all) has 100 political prisoners. In lieu of plain execution he decides to pose them a problem so that some of them can escape if they are smart enough. At random each of them will have a hat placed on his head. This hat may be red green or blue and no prisoner knows what colour his own hat is. The prisoners will all be stood in a line facing the same way so that each can see all the people in the line infront of him. Starting at the back of the line the guards will ask each prisoner in turn what colour his hat is with death being the punishment for an incorrect answer. Each prisoner will have heard the answer given by the man behind him and the result of that answer. The prisoners are given time to discuss between them a strategy for saving themselves. How many prisoners can you save? An example of a rubbish strategy might be: if the guy behind gets executed you repeat what he said if the guy behind lives you say the colour of the guy infront of you's hat first guy says the guy in front's hat That should save at least half of the prisoners Russell PS i believe the guy who posed this question to me found it on tinterweb so no googling for spoilers.
When I tried it the first prisoner was Chuck Norris. It didn't end very well for the guards.
Using the GridView is like trying to explain to someone else how to move a third person's hands in order to tie your shoelaces for you. -Chris Maunder
-
Russell Jones wrote:
At random each of them will have a hat placed on his head. This hat may be red green or blue and no prisoner knows what colour his own hat is.
If the choice of hats is truly random, then there is no relationship between the hat color of one prisoner and that of another. The odds of any prisoner having any particular hat color is 1 in 3. Knowing the hat colors of all those in front of you is not useful (in fact it is not useful to know all the other hat colors, since any color you guess for your own hat still has a 2 in 3 chance of being wrong.) any strategy will have the same result: 1/3 will survive, since they have a 1 in three chance that their guess will be right.
-
Buddy, you know, this really won't work if you keep changing the rules.
Cheers, Sebastian -- "If it was two men, the non-driver would have challenged the driver to simply crash through the gates. The macho image thing, you know." - Marc Clifton
Fair point, The idea of the puzzle is that the message is what's important not the way it is said or the timing of it. Russ
-
When I tried it the first prisoner was Chuck Norris. It didn't end very well for the guards.
Using the GridView is like trying to explain to someone else how to move a third person's hands in order to tie your shoelaces for you. -Chris Maunder
Brilliant
-
It's actually better than chance: warning potential spoiler: http://www.msri.org/people/members/sara/articles/hat.html[^]