Author |
Topic: SINGLE-FILE HAT EXECUTION (Read 17305 times) |
|
oneself
Newbie
Posts: 1
|
 |
SINGLE-FILE HAT EXECUTION
« on: Jul 28th, 2002, 9:34pm » |
 Quote  Modify
|
Single-File Hat Execution
This one is really giving me the run around.
The hint says you can guarantee N-1 saved. But I was thinking
and really only the first prisoner can pass along information to the others,
and maybe die, at that point everyone else MUST know what color
hat they have on AND use that information to save themselves.
Therefore they can not pass along any more usefull information, unless
they say their answer in a low voice which means the next guy has a
blank hat on or a high voice if it's white. Only I hope that is not the
answer.
If half the prisoners sacrifice themselves they can save the other half,
by saying what color that hat in front of them is instead of their own.
But that only gaurantees N/2.
That is my best solution so far.
//Link added and Title changed by moderator//
|
| « Last Edit: Aug 28th, 2003, 6:33pm by Icarus » |
 IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
|
Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
« Reply #1 on: Jul 29th, 2002, 1:58pm » |
Quote Modify
|
There's no voice intonation tricks; if the problem had that much freedom, it would be trivial ... people could tap each other on the shoulder, or use mutant telekinesis powers.
It is not exactly true that what the 10th prisoner says (I refer to the 10th prisoner as the last person in line, who is the first person the executioner prompts) can convey the colors of everyone's hats. This was what I thought at first as well.
However, it is true that what the 10th prisoner says should reveal the color of the 9th prisoner's hat.
Then, the 8th prisoner should be able to figure out his or her hat color based on information given by both the 9th and 10th prisoners.
The 7th prisoner uses information from the 8th, 9th, and 10th prisoners. And so on. So there's a cascading effect.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Gamer555
Newbie
Posts: 19
|
|
Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
« Reply #2 on: Jul 29th, 2002, 7:54pm » |
Quote Modify
|
Much of this is (including this and Greedy Pirates) is called (By me) "Yes, Yes, Yes" tactics (which was a problem like this, only WAY simpler) because like what da cool moderator said, you can make your decision based on what the others said.
My question is, does the solution involve sure things (like there is a logic that will say what is going on) used by the prisoners to obtain maximum saving, or is there probability (like kill yourself if there are more black hats then white, and don't if there are more white hats then black)
My (partial) solution is:
10: Kill yourself if 1,2,3 have more blacks than 4,5,6
9: Kill yourself if 2,3,4 have more blacks than 5,6,1
8: Kill yourself if 3,4,5 have more blacks than 6,1,2
7: ?
Will this work if 7 is given a boolean statement? Or is boolean logic out altogether?
|
|
IP Logged |
|
|
|
Jon
Guest
|
|
Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
« Reply #3 on: Jul 30th, 2002, 7:36am » |
Quote Modify
 Remove
|
Look at the thread titled "Single file execution - want hint" or something like that for a discussion and the solution and a walkthrough.
jon
|
|
IP Logged |
|
|
|
Peter
Newbie
Gender:
Posts: 3
|
|
Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
« Reply #4 on: Jul 30th, 2002, 10:19am » |
Quote Modify
|
I’m intrigued at how straight-jacketed men could tap one another on the shoulder but I don’t think it helps resolve this problem!
By definition Guy 10 can only communicate “black” or “white”. I assume if he says anything else he is executed and the game starts all over for the remaining 9. So, for sake of example let’s assume he says “black” what might this mean?.
a) black could be the most prevalent colour and if everyone follows suit this only guarantees a minimum of 5 but 10 on a good day! Also, Guy 9 could ‘take a dive’ here and that compromises ‘n-1’ if 10 has already ‘copped it’.
b) black could be the colour of hat 9 and if all the even Guys declare the colour of the hat of the odd Guy in front of them we should, on average save 7.5 and on a good day 10 but no guarantee of 5+ here.
If we know the number of, say, black hats its all very easy everyone keeps a tally of “black” declarations, adds the number of black hats they see and subtract that sum from the known number to deduce their hat colour.
The dilemma I can’t resolve is how Guy 9 can communicate anything other the colour of his own hat, he must say that colour if he is to live and with a guaranteed ‘n-1’ I assume poor old 10 is the possible (he might fortuitously say his hat colour) ‘Fall Guy’.
Does exclusion of intonation also disallow a delay in response being a means of communication? It will work as each Guy is asked a question and no delay could mean your hat is the same colour as I'm saying and a delay means otherwise.
I’m rambling, .............. does any of this help?
|
|
IP Logged |
|
|
|
Peter
Newbie
Gender:
Posts: 3
|
|
Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
« Reply #5 on: Jul 30th, 2002, 2:47pm » |
Quote Modify
|
Nope, it doesn't help at all, what does is looking at alternative forum board "single file execution (want hint)". Over & out!
|
|
IP Logged |
|
|
|
Charlie949
Newbie
Common sense is not so common...
Gender:
Posts: 2
|
|
Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
« Reply #6 on: Aug 1st, 2002, 6:32pm » |
Quote Modify
|
When this problem was first posed to me it involved 50 prisoners. I found a non-optimal but decent solution.
Let the first 6 prisoners who speak use the words "black" and "white" to signify one's and zero's in a binary number. This number can represent 0 <= x <= 64. This value can indicate the number of black hats (WLOG).
The optimal solution can be found at http://www.freuman.com/puzzles.htm
|
|
IP Logged |
|
|
|
Luni_B
Newbie
Are you afraid to die or just to live?
Gender:
Posts: 4
|
|
Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
« Reply #7 on: Aug 2nd, 2002, 12:36am » |
Quote Modify
|
i thought about this one for a couple minutes...but i can save 9 of the 10 (also N-1) lives guarenteed, with a 50% chance of total salvation! :
It is agreed upon that the person ANSWERING first (last in line) will answer BLACK for an ODD, and WHITE for an EVEN. Odd/Even applying to only ONE color hat(must be memorized by all...we'll say they picked BLACK to be the counted color)
Reguardless of whether the 1st person answered correctly, the rest of them can now deduce what color hat they have on by counting the same color hats in front of themselves.
For instance:
1st person answers = BLACK (odd)...
now 2nd person counts the black hats in front of himself and finds an odd number, therefore he knows his hat is white (for those not following: if he counts and finds odd he CAN'T have black on or the count would have come up even when the 1st person counted).
The 3rd person now knows his hat is BLACK, because its even in front of him.
The 4th person, knowing that the 3rd must have counted even, starts the whole process over again, bearing in mind that the person behind him saw an EVEN number of black hats...
etc etc etc - if you don't follow by now you won't.
FINALLY note that the 1st person to answer did so based solely on his count, therefore he had 50% of dying...
|
|
IP Logged |
|
|
|
jograd
Guest
|
|
Re: SINGLE-FILE HAT EXECUTION -SOLUTION
« Reply #8 on: Aug 2nd, 2002, 2:14am » |
Quote Modify
Remove
|
This is your solution.
And this accounts for the N-1 probability.
Every man says the color of the hat of the man in front of him starting with the last guy.
Now the last guy answers first and he will never know what color his hat is. He has a 50/50 chance of living. He is the "-1" in the "N-1" probability. Therefore he will take a chance and say what color the hat of the man in front of him is and this goes down the line to the first guy and so everyone is sure to be saved except the last guy (#10).
|
|
IP Logged |
|
|
|
Andrew Ooi
Guest
|
|
Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
« Reply #9 on: Aug 8th, 2002, 11:03pm » |
Quote Modify
Remove
|
jograd, try your solution with a BWBWBWBWBW combination and see how well it works 
There is another thread to this [single file execution (want hint)] same question where I have posted a generalized solution for N prisoners and K colour hats, where N-1 prisoners are guaranteed to survive and the remaining prisoner has a 1/K chance of survival.
|
|
IP Logged |
|
|
|
pranava
Guest
|
|
Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
« Reply #10 on: Jun 5th, 2003, 11:53pm » |
Quote Modify
Remove
|
All the prisoners got together and decided that they shout a number and colour. This would be similar to the roll call of people.
Eg. the 10th guy would shout "10 black" to signify the colour of caps on next two people in the row. (1: white, 0: Balck)
for exapmle if the arrangement is
BWWBBWBBWW
the 10th guy would shout : 11 Black
9 th: 10 white.
and goes on...
the 10th guy always says black....
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
« Reply #11 on: Jun 6th, 2003, 4:58pm » |
Quote Modify
|
The prisoners are only allowed to say "Black" or "White". Luni_B gives the best solution possible with no other means of communicating anything other than 1 of the two colors(though you will find it better explained on the other thread for this puzzle)
To summarize:
- The prisoners agree in their meeting that the first person will call "black" if he sees an even number of black hats. Otherwise, he says "white".
- Each remaining prisoner counts the number of "blacks" called out behind him, and the number of black hats he can see. If on his turn the total is odd, he must have on a white hat. If the total is even his hat must be black. He calls out the appropriate color.
The same logic will work for any number K of colors, except that you have to identify each color with an integer from 0 to K-1. The first guy adds up the numbers for all the hats in front of him, and figures out what additional number must be added to bring the total to a multiple of K. He calls out the corresponding color. Everyone else adds up the colors they see and the colors they hear, and also figure out what is missing to get to a multiple of K. That is the color of their hat.
There is no way for the first guy to ever have a better than 1/K chance of surviving - he must make his call without any information at all. But this guarantees the others will live. The only drawback is that you've got to have a "team player" in that first slot. You definitely don't want someone who would like to see everyone else dead!
|
|
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
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
« Reply #12 on: Jun 10th, 2003, 9:33am » |
Quote Modify
|
Icarus,
That's an interesting point--what if the very first person says the wrong colour? (incompetence, malicious intent, etc). If we know that the second person in line is following the strategy and still gets killed then the subsequent people in line can mentally reverse the answers of the first two to guarantee their survival.
But if person #2 assumes that person #1 was lying, but was wrong about it, then reversing the answers would get #3 killed. Of course if person #2 assumes that person #1 was lying and was right about it, then person #3 will die if he doesn't reverse his answer. Allowing maliciousness brings us much closer to the original 50/50 chance of dying...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
« Reply #13 on: Jun 10th, 2003, 9:28pm » |
Quote Modify
|
You can divide the prisoners into two types:
Lying-Suspicious-Stupid = says the opposite of what the scheme indicates.
Truthful-Trusting-Smart = says exactly what the scheme indicates.
Every time in the lineup that a LSS follows a TTS or a TTS follows an LSS, he dies.
Therefore, it is in the best interests of everyone (except the unhelpable #1) to try and minimize the number of transistions. So if you know that #1 is a slimy bastard, you let everyone know that they ought not trust him (so that He doesn't hear it of course). If not, then make sure everyone else is in complete agreement. But most particularly you want to make sure you know the demeanor of the guy immediately behind you. If you can agree with him, then you are safe, no matter what happens to everyone else.
|
| « Last Edit: Aug 18th, 2003, 3:24pm 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
|
|
|
Non-entity
Guest
|
|
Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
« Reply #14 on: Jul 22nd, 2003, 7:10pm » |
Quote Modify
Remove
|
forgive me for not reading every post.
I am the ninth person in line. I have been notified by the person behind me that my hat is black. The hat in front of me is white. How do I save myself (by saying black) and notify the person in front of me that his hat is white?
with the only signals I can say being "black" or "white" I am at a loss to save n-1.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
« Reply #15 on: Jul 23rd, 2003, 4:44pm » |
Quote Modify
|
If you want a hint: The first guy does not simply announce your hat color. He has to make an announcement that will allow everyone to deduce their own hat color from all the announcements they hear from behind and what they see in front of them.
If you want the full answer, read the posts - there are not that many of them.
|
|
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
|
|
|
coderyogi
Newbie
Posts: 29
|
|
Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
« Reply #16 on: Mar 4th, 2010, 8:27am » |
Quote Modify
|
on Jun 6th, 2003, 4:58pm, Icarus wrote:
The same logic will work for any number K of colors, except that you have to identify each color with an integer from 0 to K-1. The first guy adds up the numbers for all the hats in front of him, and figures out what additional number must be added to bring the total to a multiple of K. He calls out the corresponding color. Everyone else adds up the colors they see and the colors they hear, and also figure out what is missing to get to a multiple of K. That is the color of their hat.
There is no way for the first guy to ever have a better than 1/K chance of surviving - he must make his call without any information at all. But this guarantees the others will live. The only drawback is that you've got to have a "team player" in that first slot. You definitely don't want someone who would like to see everyone else dead! |
|
If I get this correct, each guy has to add ALL previous calls made by other guys and then add this number to the addition of colors he can see out front to get his hat number? Coz as far as i can see, just remembering the previous call does not get the required color number.
|
| « Last Edit: Mar 4th, 2010, 8:28am by coderyogi » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
« Reply #17 on: Mar 4th, 2010, 9:12am » |
Quote Modify
|
on Mar 4th, 2010, 8:27am, coderyogi wrote:
If I get this correct, each guy has to add ALL previous calls made by other guys and then add this number to the addition of colors he can see out front to get his hat number? Coz as far as i can see, just remembering the previous call does not get the required color number. |
|
Yep.
The first guy to speak describes a property of the entire line (apart from himself), so that changing the colour of any one hat would change what he says.
By listening to other people (correctly) identifying their own hats, and observing the hats in front of them, by the time they speak, every prisoner knows the colour of every hat other than their own (and the first guy's) so can use the first prisoner's statement to save themselves.
|
|
IP Logged |
|
|
|
coderyogi
Newbie
Posts: 29
|
|
Re: SINGLE-FILE HAT EXECUTION - HINT PLEASE?
« Reply #19 on: Mar 5th, 2010, 11:00pm » |
Quote Modify
|
on Mar 4th, 2010, 9:12am, rmsgrey wrote:
Yep.
The first guy to speak describes a property of the entire line (apart from himself), so that changing the colour of any one hat would change what he says.
By listening to other people (correctly) identifying their own hats, and observing the hats in front of them, by the time they speak, every prisoner knows the colour of every hat other than their own (and the first guy's) so can use the first prisoner's statement to save themselves. |
|
Thanks!
|
|
IP Logged |
|
|
|
rohigoyal86
Newbie
Posts: 2
|
|
Re: SINGLE-FILE HAT EXECUTION
« Reply #20 on: Nov 22nd, 2011, 2:39pm » |
Quote Modify
|
10th guy has to say BLACK(if no. of caps which are more are in odd no.)
otherwise he will say white ( if no. of caps which are greater are in even no.)
suppose there are 9 guys in front of him
so cases may be
odd is greater;
7,2 ;
5,4;
9,0;
or even is greater;
6,3;
8,1;
in this way 9 can find out by counting no. of coloured hats which are in greater no.
slly by hearing his reply others can calculate.
10 and 9 have a probability of dying i.e 1/2.
rest 8 would be saved.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: SINGLE-FILE HAT EXECUTION
« Reply #21 on: Nov 23rd, 2011, 9:46am » |
Quote Modify
|
on Nov 22nd, 2011, 2:39pm, rohigoyal86 wrote:10th guy has to say BLACK(if no. of caps which are more are in odd no.)
otherwise he will say white ( if no. of caps which are greater are in even no.)
suppose there are 9 guys in front of him
so cases may be
odd is greater;
7,2 ;
5,4;
9,0;
or even is greater;
6,3;
8,1;
in this way 9 can find out by counting no. of coloured hats which are in greater no.
slly by hearing his reply others can calculate.
10 and 9 have a probability of dying i.e 1/2.
rest 8 would be saved. |
|
Actually, by my calculations, your method will save everyone except those who see/hear four of each colour (and a "Black" from #10) and #10 himself. If the colours are split 5-4 (ignoring #10's cap) then the five with the majority colour are at risk initially. If mistakes are executed immediately, then only the first to guess wrong will die; if the executions wait until the end, then those wearing the other colour are reduced to guessing after each mistake - if cap colours alternate, then all ten could guess wrong...
|
|
IP Logged |
|
|
|
rohigoyal86
Newbie
Posts: 2
|
|
Re: SINGLE-FILE HAT EXECUTION
« Reply #22 on: Nov 23rd, 2011, 3:17pm » |
Quote Modify
|
on Nov 23rd, 2011, 9:46am, rmsgrey wrote:
Actually, by my calculations, your method will save everyone except those who see/hear four of each colour (and a "Black" from #10) and #10 himself. If the colours are split 5-4 (ignoring #10's cap) then the five with the majority colour are at risk initially. If mistakes are executed immediately, then only the first to guess wrong will die; if the executions wait until the end, then those wearing the other colour are reduced to guessing after each mistake - if cap colours alternate, then all ten could guess wrong... |
|
suppose it is 5 and 4 . 9th guy will sees 4 white and 4 black .the he can say any colour.so his probability of living is .5 in that case.
now trick is that if he says wrong colour he will die. other will soon know that he has said wrong colour.also if he 9th says the right colour then colour in front of 8th are in ratio 4;3 and he also knows color of hat of 9th guy through this he can deduce his color of hat
|
| « Last Edit: Nov 23rd, 2011, 3:41pm by rohigoyal86 » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: SINGLE-FILE HAT EXECUTION
« Reply #23 on: Nov 24th, 2011, 8:45am » |
Quote Modify
|
on Nov 23rd, 2011, 3:17pm, rohigoyal86 wrote:
suppose it is 5 and 4 . 9th guy will sees 4 white and 4 black .the he can say any colour.so his probability of living is .5 in that case.
now trick is that if he says wrong colour he will die. other will soon know that he has said wrong colour.also if he 9th says the right colour then colour in front of 8th are in ratio 4;3 and he also knows color of hat of 9th guy through this he can deduce his color of hat |
|
If #9's hat is black and #8 sees 4 white and 3 black, #8 knows it's 5-4, whichever colour his hat is, but doesn't know whether #9 saw 5 white and 3 black and knew his own hat must be black, or 4 white and 4 black and guessed right. If he always guesses white in that situation, #8 has a 2/3 chance of being right (assuming the hats were assigned independently so each has a 50% chance of being white).
If #9's hat is black and #8 sees 3 white and 4 black (and #10 signalled the larger group to be odd) then #8 knows his hat must be white and is safe.
If #7 then sees three of each, knowing that there's a black and a white behind him, and that nobody has yet guessed wrong, then he has to guess, with a 60% chance of having a black hat.
And so on. I'm not going to bother computing the other variations for #7 or the variations for #6 onward. The point is that (until someone dies), anyone who knows that there are 4 black and 4 white (and #10's hat) aside from their own hat can't be sure whether the 5-4 is 5 blacks or 5 whites - they'd have heard and seen exactly the same things in either case.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print