Author |
Topic: single file hat execution (Read 15498 times) |
|
klbarrus
Newbie
Posts: 29
|
 |
single file hat execution
« on: Jul 25th, 2002, 11:09pm » |
 Quote  Modify
|
Single File Hat Execution
I'm not sure I have the solution for this problem. Here is what I have:
Each prisoner needs to call out their hat color, and also give some info to the next prisoner in line. So they agree to indicate the next prisoner's hat color by pausing when they call their own. No pause = white, pause = black. (or loud = white, soft = black, whatever).
This way, everybody except the 10th prisoner will get their color correct. The 10th prisoner takes his 50% guess, but gives the appropriate info to the 9th and the rest can save themselves.
Any other solutions?
/ Edited by Moderator to add link and clean up title. /
|
| « Last Edit: Aug 28th, 2003, 4:56pm by Icarus » |
 IP Logged |
|
|
|
dlau
Newbie
Posts: 3
|
|
Re: single file execution (want hint)
« Reply #1 on: Jul 25th, 2002, 11:52pm » |
Quote Modify
|
you can save on average 9.5 people just by saying the color hat, no additional information required.
heres a big hint:
*spoiler space*
think about parity
|
|
IP Logged |
|
|
|
Tan
Guest
|
|
Re: single file execution (want hint)
« Reply #2 on: Jul 26th, 2002, 5:01am » |
Quote Modify
 Remove
|
Black/White Hat or rather Even/Odd problem
--------------------------------------------
All prisoners agrees that whoever becomes the 10th prisoner, will count the hats in front of him.
Shouts Even if he counts even number of black hats infront of him (he cannot see his own)
Shouts Odd if he counts odd number of black hats infront of him.
10th prisoner: He counts the 9 hats in front of him. If he sees Even number of black hat, shouts Even, Odd number shouts Odd
9th prisoner: He heard that the 10th prisoner shout Even. He counts the 8 hats in front of him , if he counts Even number of Black hats, he knows he himself must be White. If he counts odd number of Black hats, he knows he himself must be Black otherwise the 10th guy is in error.
So on & so forth. If the prisoners are all intelligent and co-operative. All except the 10th prisoner have absolute chance of getting it correct. Probability of the 10th prisoner getting it correct is only 50%.
Now the problem is that shouting "even" & "odd" is against the rule for the 10th prisoner. Therefore he shouts :
"Black to represent Even" and
"White to represent Odd".
The rest of the prisoners can deduce their own hat colors and just shout their own hat color. This allows those subsequently down the line to save themselves too.
Therefore 9.5 person saved !
|
|
IP Logged |
|
|
|
klbarrus
Newbie
Posts: 29
|
|
Re: single file execution (want hint)
« Reply #3 on: Jul 26th, 2002, 10:22am » |
Quote Modify
|
Oh! I thought the prisoners could only say their hat color and nothing else.
|
|
IP Logged |
|
|
|
jon
Guest
|
|
Re: single file execution (want hint)
« Reply #4 on: Jul 26th, 2002, 2:09pm » |
Quote Modify
Remove
|
they only do say black or white. The point is that #10 is speaking in code.
Here's a concrete example:
From 1 to 10, the colors are:
BBWWWBBWBB
#10 sees 5 black hats so he says "white" (the prisoners previously agreed that "white" means odd for #10). (He's wrong, so he dies. That doesn't matter).
#9 sees 4 black hats. He then deduces his hat is black, and says "black."
#8 sees 4 black hats. adding the one that #9 declared, 4+1 = 5, which matches what #10 said, so he concludes he is white and says "white."
#7 sees 3 black hats. 3 + 1 (from #9) = 4, which doesn't match what #10 said, so he concludes he is black and says "black"
#6 sees 2 black hats. 2+2 (from #9 and #7) = 4, which doesn't match. So he says "black"
# 5 sees 2 black. 2+3 (from #9, #7, #6) = 5, which matches. So he says "white."
#4 and #3 are the same as #5.
#2 sees one black hat. 1+3 = 4, which doesn't match, so he says "black.
#1 sees no black hats (of course). he's heard 4 people say "black" but the total is odd, so he knows he's black.
that is a lovely problem.
|
|
IP Logged |
|
|
|
klbarrus
Newbie
Posts: 29
|
|
Re: single file execution (want hint)
« Reply #5 on: Jul 26th, 2002, 7:09pm » |
Quote Modify
|
Ah... silly me. I was confused by your quotation marks:
"black to represent even" should really be "black" to represent even 
|
|
IP Logged |
|
|
|
thebean
Guest
|
|
Re: single file execution (want hint)
« Reply #6 on: Jul 26th, 2002, 7:46pm » |
Quote Modify
Remove
|
It's true that the 1st prisoner is taking a 50/50 chance, but all other prisoners can be saved if the 1st prisoner and every subsequent prisoner simply says the color of hat on the next guy in line. No 'parity' calculations involved...
|
|
IP Logged |
|
|
|
Rhaokarr
Guest
|
|
Re: single file execution (want hint)
« Reply #7 on: Jul 26th, 2002, 8:38pm » |
Quote Modify
Remove
|
The problem with that, bean, is that if the hat in front of you doesn't match yours, you're executed, as you have just called out the wrong colour.
|
|
IP Logged |
|
|
|
TheBean
Guest
|
|
Re: single file execution (want hint)
« Reply #8 on: Jul 28th, 2002, 10:27pm » |
Quote Modify
Remove
|
Doh!, I shouldn't do these things late at night. I could get some prisoners killed somewhere that way....
|
|
IP Logged |
|
|
|
Gamer555
Newbie
Posts: 19
|
|
Re: single file execution (Have we got it?)
« Reply #9 on: Jul 29th, 2002, 7:58pm » |
Quote Modify
|
Great solution!
|
|
IP Logged |
|
|
|
Gamer555
Newbie
Posts: 19
|
|
Re: single file execution (want hint)
« Reply #10 on: Jul 30th, 2002, 9:43am » |
Quote Modify
|
Does the problem state that they won't be killed then and there? I thought about it, and if they get killed there, 10 will just say what his is, and then get saved. Then 9 will know what color the other 8 are, and 10's hat so he can save himself. Does this solution work too?
|
|
IP Logged |
|
|
|
Jon
Guest
|
|
Re: single file execution (want hint)
« Reply #11 on: Jul 31st, 2002, 12:39pm » |
Quote Modify
Remove
|
no, for two reasons:
1) 10 can't see his own hat, so he doesn't know the color.
2) Even if for some reason he could see his own hat, 10 *must* communicate the parity of the black hats to the remaining line by using the even=black/odd=white code. Otherwise, the other prisoners wouldn't know what to do.
|
|
IP Logged |
|
|
|
jograd
Guest
|
|
Re: single file execution (want hint)
« Reply #12 on: Aug 2nd, 2002, 2:42am » |
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 |
|
|
|
mook
Guest
|
|
Re: single file execution (want hint)
« Reply #13 on: Aug 3rd, 2002, 9:17am » |
Quote Modify
Remove
|
my solution was that each person would say the number of black hats that they saw in front of them by repateing their color i.e. if #10 sees 6 black hats in front of him, he will say:"black, black, black, black, black, black", #9, still seeing 6 black hats will say "white, white, white, white, white, white" and so forth. The quaestion states that they can only guess their color, but it doesn't say that they can't repeat it. In truth though, the odd/even system seems more efficient, after all, if #10 guesses wrong, he might be dead before he gets to the 3rd "black"
|
|
IP Logged |
|
|
|
Andrew Ooi
Guest
|
|
Re: single file execution (want hint)
« Reply #14 on: Aug 8th, 2002, 8:22pm » |
Quote Modify
Remove
|
Since nobody gave the generalized solution for N prisoners with K colour hats, here it is (guaranteed N-1 survivors):
1) Assign 0,1,2,3...K-1 to each colour (colour values) - all prisoners must memorize these mappings.
2) The last prisoner sums up the colour values of all hats he sees in front of him (S), and calls out the colour of (S mod K) which we will call S'. He has a 1/K chance of escaping alive.
3) Any prisoner in the line will take note of S' which is (S mod K), and will subtract modulo K from S' for each colour value he hears from behind him. For example if K=7, his current S' = 4, and he hears a colour value of 5 from behind him, then his new S' is 6 ((4-5) mod 7 = 6 mod 7).
4) When it is the prisoner's turn then he'll count the sum of those in front of him to get S*, and (S*-his latest S') mod K will give him the colour value of his own hat.
|
|
IP Logged |
|
|
|
Jamie Walch
Guest
|
|
Re: single file execution (want hint)
« Reply #15 on: Aug 30th, 2002, 4:30am » |
Quote Modify
Remove
|
I heard this problem a few weeks ago and came up with a further, if somewhat tenuous generalisation. If we assume (a) that everyone has excellent colour vision, and (b) that we are allowed to get the colour approximately right (ie. if our hat is crimson and we say 'bright red', we're okay), then we don't need any prior information about what the possible set of colours can be. In fact everyone can be wearing a different colour, and we can still, in theory, save all but the guy at the back.
Note: I did say 'in theory' 
Jamie
|
|
IP Logged |
|
|
|
vijk
Guest
|
|
Here's the general solution
« Reply #16 on: Aug 30th, 2002, 9:47am » |
Quote Modify
Remove
|
Hi,
this is a general solution for the k coloured hats.
The prisoners assign each color a unique number <k(including 0).
Each prisoner remembers the color shouted by the one before him(b) and finds his color(h) such that
(h+sum of colors in front of him)mod k=b.
This is easier than it sounds.
This needs the 10th prisoner to take a chance of probability 1/k since he has no one to shout before him.
Assume there are 5 prisoners and 3 colors of hats. hat colors are 0,1,2.
They are arranged in a file like this:
54321(prisoners)
02101(colors)
Here n=5,k=3.
p5(prisoner 5) shouts (2+1+0+1)+(0)(no one shouted before him)=(4 mod 3)=1 . In this case he dies.
now for p4, b=1, he has to find h such that
(h+(1+0+1))mod 3= b
ie, h+2 mod 3 = 1, so, h=2. p4 shouts 2.
for p3, b=2,
(h+ (0+1)) mod 3=2
h+1 mod 3=2.
so h is 1.
And so on.
For 2 color hats, this operation is same as XOR.
|
|
IP Logged |
|
|
|
wowbagger
Uberpuzzler
 
Gender: 
Posts: 727
|
|
Re: single file execution (want hint)
« Reply #17 on: Sep 4th, 2002, 4:40am » |
Quote Modify
|
vijk: Your solution is close, but not correct. In the example given (K=3, p1..p5=10120), the next steps would be:
for p2, b=1,
(h + 1) mod 3 = 1, so h = 0 (correct, p2 saved)
for p1, b=0,
h mod 3 = 0, so h = 0 => p1 will get killed!
Here's my proposal:
assign a number in [0,...,K-1] to every colour (uniquely, of course);
each prisoner p_j (1<=j<=N) calculates the sum N_j (mod K) of the colours of the hats in front of him;
prisoner p_j says the colour that corresponds to h_j such that:
N_j + h_j + sum_{i=j+1..N} h_i = K-1 (mod K)
So every prisoner adds the sum of hat colours in front of him (N_j) and the sum of colours already told by prisoners with higher numbers (sum over h_i).
Personally, think the above formula is fairly easy to use as it only involves addition, no subtraction (mod K).
In the case of vijk's example, we have:
1 2 3 4 5 number of prisoner (j)
1 0 1 2 0 hat colour
p5 has N_5 = (1+0+1+2) mod 3 = 1
=> h_5 = 1 (bad luck!)
p4: N_4 = 2, sum of colours told so far = 1,
2 + h_4 + 1 = 2 (mod 3)
=> h_4 = 2
p3:
1 + h_3 + (1+2) = 2 (mod 3)
=> h_3 = 1
p2:
1 + h_2 + (1+2+1) = 2 (mod 3)
=> h_2 = 0
p1:
0 + h_1 + (1+2+1+0) = 2 (mod 3)
=> h_1 = 1
Test it using other values for K, it works.
I hope you will agree this solution guarantees to save at least N-1 prisoners.
|
| « Last Edit: Sep 9th, 2002, 1:47am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: single file execution (want hint)
« Reply #18 on: Sep 6th, 2002, 5:58pm » |
Quote Modify
|
Quote:| I heard this problem a few weeks ago and came up with a further, if somewhat tenuous generalisation. If we assume (a) that everyone has excellent colour vision, and (b) that we are allowed to get the colour approximately right (ie. if our hat is crimson and we say 'bright red', we're okay), then we don't need any prior information about what the possible set of colours can be. |
|
This trivially reduces to the case of "k hats of known colors". Allowing "approximate colors" lets us break down the set of all colors into a finite set. For instance, {red orange yellow green blue purple black gray white}, if we consider all colors to be "approximately" one of those colors (if we need better approximations than that, we put more colors into our set). Then, we just say that those 9 colors (or however many there are) are the k different colors of the general case, and we use the modular addition method.
|
|
IP Logged |
|
|
|
Michael Gregory
Guest
|
|
I think I have a simpler solution
« Reply #19 on: Oct 16th, 2002, 9:08pm » |
Quote Modify
Remove
|
Why not just have each prisoner shout as loud as possible if the hat in front of them is black, and speak at a normal volume if the hat in front of them is white?
If the first guy happens to have the same color hat as the second guy, good for him. Else, he dies. But he's the N-1.
So if the volume is taken to be the code, then everyone else should be able to save each other- and none of this math you speak of is involved. If I was about to die, I'd want things as simple as possible, cause I'd be pretty damn nervous.
Any holes in my logic?
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: single file execution (want hint)
« Reply #20 on: Oct 16th, 2002, 9:58pm » |
Quote Modify
|
You should assume that each prisoner can send only one bit of information when the executioner awaits a response, thereby restricting any such extra signals that would make the riddle trivial (e.g. tapping the person in front of you on the shoulder, sneezing, voice intonations, ninja hand signals, esp). I guess I should have stipulated that in the problem.
|
| « Last Edit: Oct 16th, 2002, 9:58pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
rmsgrey
Guest
|
|
Re: single file execution (want hint)
« Reply #21 on: Apr 12th, 2003, 12:52pm » |
Quote Modify
Remove
|
There's a simple proof that there're precisely two unique "best" solutions to the binary version of the puzzle:
The guy at the back has a choice of two things to say - either "black" or "white" - pick a combination (say all white) for what he sees in front of him and pick one of his two options (say white). Since, by assumption, the best solution allows everyone to get their hat colour right, everyone else always says the colour of their own hat. For your code, the intial choice of colour to say when faced with all white defines the rest of the code - to save everyone, you need to invert the first colour if a single hat differs - if there's one black hat, then if you don't say black for your code (assuming you chose white for all whites) the guy with the black hat hears all whites behind him and sees all whites in front whether he's wearing black or white...
Another sidenote on the problem is to consider the situation where execution is delayed until after everyone has guessed - in which case it becomes a question of how trustworthy the people behind you are...
Of course, instant executions tell you immediately what colour hat the person actually had on, so the only person in a position to kill people is the sucker at the back (who feels bitter because he's stuck with the 50% bullet). In any case, since it's a load of prisoners, wondering about trustworthiness is probably justified.
|
|
IP Logged |
|
|
|
Yoda
Newbie
Posts: 11
|
|
Re: single file execution (want hint)
« Reply #22 on: Aug 18th, 2003, 8:31am » |
Quote Modify
|
Trustworthiness is an interesting problem. EVEN IN THE CASE OF INSTANT EXECUTIONS.
And really it turns the problem into a fifty-fifty without extra information about the probability of lying and the probability of distrusting (you need both) because if the ninth guy believes the last guy and dies, then the eighth guy could still make the correct guess as long as he knew that the 9th guy believed the 10th guy was calling out according to the parity scheme. However, the 9th guy might have distrusted the 10th guy, when the 10th guy was in fact a straight player. The ninth guy dies and now the 8th guy is left wondering did the 10th guy lie or did the 9th guy distrust the 10th guy. And what's worse, if the 9th guy lived, maybe it's because the 10th guy lied AND the 9th guy distrusted him.
IF -HUGE IF- we knew that 10th guy was going to play by the parity rule, then the canonical solution holds. Because we assume that nobody has a death wish and the only way to thwart someone else would be to effectively commit suicide.
So I don't buy the canonical solution because there is no reason for the 10th guy to play along. It's 50-50 for him anyway.
Here's a n interesting add on which is easy of you solved the original problem. Suppose nine of the ten guys have a grudge against the other guy. AND that the nine guys can completely believe and trust each other. And that this other guy is completely unsuspecting. Show that they can conspire to kill the guy that they dislike. (Ok there is 1 in 20 chance that the guy they hat will survive).
As an aside, I think the way for the players to assure themselves of the canonical solution is to find some way to incentivise the 10th player to play along. For example, a contract is drawn up with money in a third party bank account that will automatically be handed over to the 10th player should the other 9 players live. The chance of death is 50-50 anyway but that pay off is better to play along. Which would you take a 50% chance of death with a 50% chance of life or a 50% chance of death with a 50% chance of life plus 1 million dollars.
|
| « Last Edit: Aug 18th, 2003, 8:43am by Yoda » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: single file execution (want hint)
« Reply #23 on: Aug 18th, 2003, 4:27pm » |
Quote Modify
|
James Fingas and I had a short discussion about this on the other thread for this puzzle, starting with the last sentence in this post. My conclusion is that every time you have a transition in the line between someone who will follow the scheme and someone who does not, the front one (who declares second) will die.
If you know the outcomes for those behind you, you can use this information to correctly decide your own case. Everytime that someone other than the back guy is executed, switch your intended response.
If you don't know, then the prisoners can be divided into two types: Those who because of stupidity, deceit, or untrusting nature will give the opposite answer from that predicted by the scheme, and those who will follow the scheme. For this case, a prisoner (other than the first) will live if and only if his predecessor is of the same type as he. So in this case it is vitally important for you to understand how your predecessor will respond. If you know this, you can be saved, even if everyone else dies.
So the strategy session should be spent in building a concensus view. This is particularly important if you do not know the execution order beforehand.
While the "official answer" is not fool-proof, it still offers significantly better than 50% odds even with less-than-perfect co-conspirators.
|
| « Last Edit: Aug 18th, 2003, 4:31pm 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
|
|
|
Yoda
Newbie
Posts: 11
|
 |
Re: single file execution (want hint)
« Reply #24 on: Aug 18th, 2003, 8:52pm » |
Quote Modify
|
Quote:| If you know the outcomes for those behind you, you can use this information to correctly decide your own case. Everytime that someone other than the back guy is executed, switch your intended response. |
|
I don't think it quite works that well when you have both lies and mistrust:
Suppose the probability of the tenth guy deceiving (not following the agreed upon scheme) is 50%.
Suppose the probability of the 9th guy believing the 10th guy is 50%.
Then here is the payoff (T=tells the truth, D=Deceives, B=Believes, M=Mistrusts):
10th 9th Result for 9th
T B Lives
T M Dies
D B Dies
D M Lives
Now if I'm the 8th player, I ask myself, "Did the 9th player believe the 10th player?" (ITB=I think he believed, ITM=I think he mistrusted). Here is the payoff table:
10th 9th 8th Result for 8th
T B ITB Lives
T B ITM Dies
T M ITB Dies
T M ITM Lives
D B ITB Lives
D B ITM Dies
D M ITB Dies
D M ITM Lives
With the proability of T,B,and ITB all at 50%. There is only a 50% of living for the 8th guy.
New problem: Suppose on the day of the execution, Lightly Lying Larry ends up as the last guy. He only deceives people about 10% of the time. Massively Mistrusting Mike doesn't know that Lightly Lying Larry only lies 10% of the time. In fact, he mistrusts everyone 90% of the time (a bit foolish and may cost him dearly this time). Now, Sally the All-knowing Psychologist, who ended up in the 8th spot, can read personalities quite well. She can't say what someone will do on a particular instance but she can guess the probability of them doing something based on their character. What is Sally's optimal strategy? What is the probability that Sally's strategy will pay off?
(It's important that Massively Mistrusting Mike doesn't know the probability of Larry Lying. If he did he would be able to optimize his solution (believe Larry) and Sally would optimize her solution assuming Mike had optimized his). Mike would have 10% chance of dying and Sally would live for sure.)
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print