wu :: forums - Print Page


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

        riddles >> hard >> single file hat execution
        
(Message started by: klbarrus on Jul 25^th, 2002, 11:09pm)

Title: single file hat execution
Post by klbarrus on Jul 25^th, 2002, 11:09pm

Single File Hat Execution (http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#singleFileHatExec)

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. /

Title: Re: single file execution (want hint)
Post by dlau on Jul 25^th, 2002, 11:52pm

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

Title: Re: single file execution (want hint)
Post by Tan on Jul 26^th, 2002, 5:01am

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 !

Title: Re: single file execution (want hint)
Post by klbarrus on Jul 26^th, 2002, 10:22am

Oh! I thought the prisoners could only say their hat color and nothing else.

Title: Re: single file execution (want hint)
Post by jon on Jul 26^th, 2002, 2:09pm

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.

Title: Re: single file execution (want hint)
Post by klbarrus on Jul 26^th, 2002, 7:09pm

Ah... silly me. I was confused by your quotation marks:
"black to represent even" should really be "black" to represent even ;)

Title: Re: single file execution (want hint)
Post by thebean on Jul 26^th, 2002, 7:46pm

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...

Title: Re: single file execution (want hint)
Post by Rhaokarr on Jul 26^th, 2002, 8:38pm

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.

Title: Re: single file execution (want hint)
Post by TheBean on Jul 28^th, 2002, 10:27pm

Doh!, I shouldn't do these things late at night. I could get some prisoners killed somewhere that way....

:-[

Title: Re: single file execution (Have we got it?)
Post by Gamer555 on Jul 29^th, 2002, 7:58pm

Great solution! ;)

Title: Re: single file execution (want hint)
Post by Gamer555 on Jul 30^th, 2002, 9:43am

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?

Title: Re: single file execution (want hint)
Post by Jon on Jul 31^st, 2002, 12:39pm

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.

Title: Re: single file execution (want hint)
Post by jograd on Aug 2^nd, 2002, 2:42am

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).

Title: Re: single file execution (want hint)
Post by mook on Aug 3^rd, 2002, 9:17am

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"

Title: Re: single file execution (want hint)
Post by Andrew Ooi on Aug 8^th, 2002, 8:22pm

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.

Title: Re: single file execution (want hint)
Post by Jamie Walch on Aug 30^th, 2002, 4:30am

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

Title: Here's the general solution
Post by vijk on Aug 30^th, 2002, 9:47am

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.

Title: Re: single file execution (want hint)
Post by wowbagger on Sep 4^th, 2002, 4:40am

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.

Title: Re: single file execution (want hint)
Post by Chronos on Sep 6^th, 2002, 5:58pm

Quote:

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.

Title: I think I have a simpler solution
Post by Michael Gregory on Oct 16^th, 2002, 9:08pm

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?

Title: Re: single file execution (want hint)
Post by william wu on Oct 16^th, 2002, 9:58pm

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.

Title: Re: single file execution (want hint)
Post by rmsgrey on Apr 12^th, 2003, 12:52pm

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.

Title: Re: single file execution (want hint)
Post by Yoda on Aug 18^th, 2003, 8:31am

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.

Title: Re: single file execution (want hint)
Post by Icarus on Aug 18^th, 2003, 4:27pm

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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027917276#11). 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.

Title: Re: single file execution (want hint)
Post by Yoda on Aug 18^th, 2003, 8:52pm

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.)

Title: Re: single file execution (want hint)
Post by rmsgrey on Aug 19^th, 2003, 7:42am

Super Sally knows the following probabilities:

Both follow: .09 M lives
Neither follow: .09 M lives
Only L follows: .81 M dies
Only M follows: .01 M dies

So if M dies, Sally knows that, with probability 81/82, M distrusted L and so she should trust L (assume he was right) and mentally correct what M said.

If M lives, then Sally has a 50% guess to make.

Net outcome is that Sally has a 90% chance of survival - just as if Mike wasn't there... In fact, running the numbers, you have the same chance of survival as you're best chance of correctly second-guessing one of the guys ahead of you.

Of course, this means that if you have Completely Credulous Clive, who believes whatever people tell him (which has provided many hours of entertainment to his fellow convicts) then everyone after Clive can automatically deduce whether the first guy told the truth.

With instantaneous executions, I believe Icarus is mistaken in his conclusion about death following transitions - because you know the actual colour of every hat other than your own, the only factor which influences your survival is whether you are right to trust/mistrust the first guy. All the death/survival of intervening people offers is information by which to judge the first guy's credibility (assuming you know something about the other guys credulity)

Of course, if you don't have the automatic correction provided by instant executions, then you do get the transitions die effect as Icarus said.

Title: Re: single file execution (want hint)
Post by Icarus on Aug 19^th, 2003, 5:32pm

on 08/19/03 at 07:42:36, rmsgrey wrote:

With instantaneous executions, I believe Icarus is mistaken in his conclusion about death following transitions - because you know the actual colour of every hat other than your own, the only factor which influences your survival is whether you are right to trust/mistrust the first guy. All the death/survival of intervening people offers is information by which to judge the first guy's credibility (assuming you know something about the other guys credulity)

Of course, if you don't have the automatic correction provided by instant executions, then you do get the transitions die effect as Icarus said.

My conclusion posted above for instaneous executions was that everyone can live. Death after transitions was only for the no-information case. (In the other thread I assumed that you would not know the outcomes of previous answers).

When I considered the other case above I rushed it too much and therefore missed that the result as stated only applies when player #1 is truthful. Those following the strategy I described (which could also be stated as "reverse the answer of anyone >1 who dies"), will live if player #1 also follows it. Those who do the reverse will die. If player #1 gives the opposite answer, everyone who follows the strategy will die and those who reverse it will live.

So in the "you know what happens behind you" situation, you live iff you correctly judge whether or not prisoner #1 answered according to the strategy, whereas in the other situation, you live iff you correctly judge whether or not the the prisoner immediately behind you answered according to the strategy.

Title: Re: single file execution (want hint)
Post by rmsgrey on Aug 20^th, 2003, 10:06am

Actually, for the delayed execution case, survival if you match the guy behind you assumes that you take what everyone says at face value, and then choose to follow or not the pattern based on what was said. If you know that several people behind you are going to go counter to the pattern, then you might be tempted to mentally correct what they say...

If you only have probabilistic information on other prisoners strategies, your best bet is to be speaking immediately after the prisoner you have the best chance to second guess.

In the instant execution case, there's rather more calculation involved.

Title: Re: single file execution (want hint)
Post by James Fingas on Aug 20^th, 2003, 11:06am

I shall model the problem as follows: there is a random sequence of 10 bits. There is a row of prisoners that will compute the XOR of the bits in front of them, and then, with probability P_i, report that answer correctly, XORed with the answer of the first prisoner. This P_i is meant to indicate whether they are likely to trust the answer of the first person, and P₁₀ is your a-priori estimate of the probability that the first person would tell the truth.

To calculate the probability in the most general way, we examine two cases: either the first prisoner to speak lied, or he told the truth. Either way has the possibility of leading to the observed combination of prisoners deaths.

P(first prisoner lied and this scenario happened) = [prod]_{prisoners i<10 that lived}(P₁₀(1-P_i)+(1-P₁₀)P_i)*[prod]_{prisoners i<10 that died}(P₁₀P_i+(1-P₁₀)(1-P_i))

P(first prisoner told truth and this scenario happened) = [prod]_{prisoners i<10 that died}(P₁₀(1-P_i)+(1-P₁₀)P_i)*[prod]_{prisoners i<10 that lived}(P₁₀P_i+(1-P₁₀)(1-P_i))

Now using Bayes' theorem, it should be evident that whichever one of these gives a higher number is the more likely under this model. If one of them is quite near 1, then you should be saying "aha! just what I would have predicted". In the real world, if your P_is are accurate, one should be significantly larger than the other. This is similar to approaches used in communication theory to decode messages (you take the observed bits and compute the most probable message that was sent).

This is a very basic model and does not take into account each prisoners' perception of the other prisoners, but it does allow the assessment of all the prisoners who have answered so far and their execution (or lack of same).

Title: Re: single file execution (want hint)
Post by Icarus on Aug 20^th, 2003, 4:24pm

on 08/20/03 at 10:06:12, rmsgrey wrote:

Since accurately predicting the strategy of your predecessor guarantees your survival, if you are able to do this, any attempt to adjust your answer because of the responses of other prisoners can only lower your chance of survival. The only reason for trying to determine the strategies of other prisoners would be to help you in determining the strategy of that guy right behind you. He alone you must match - nothing else matters.

Quote:

If you only have probabilistic information on other prisoners strategies, your best bet is to be speaking immediately after the prisoner you have the best chance to second guess.

Regardless of what information you have, this is still true.

Quote:

In the instant execution case, there's rather more calculation involved.

No - I would say that if anything, there is less. Now your survival depends on determining whether or not the 1st prisoner's response will be in accordance to the strategy or not. Regardless of the other players, if you can do this (by calculation or luck), you will live, if you cannot, you will die. Since the first prisoner's response is not influenced any of the other prisoners' responses, it might be easier to "get inside his head", than it would be to do so for the guy right behind you.

Thinking it over: The instantaneous execution situation gives you a choice: If there is anyone behind you whose approach you can definitely figure out, you are guaranteed to live:

Say that you know prisoner L so well, that you can predict what he will say in any situation. By luck, he is somewhere behind you. For your part, your only interest in the answers of those before L is in deciding what L will answer on his turn if he sees an odd number of white hats in front of him. If his actual answer is what you expected, treat it a response of "white", otherwise as a response of "Black". Everyone after L, you use their fate to correct the response (count "White & lived" or "Black & died"). If the result of the count plus the number of white hats before you is odd, say "white", otherwise "black". Effectively, this allows you to treat prisoner L, whom you can best predict, as if he were the first prisoner.

So my conclusion: If you don't know the outcomes of earlier prisoners, you need to correctly predict the response of the prisoner immediately behind you (dependent on how many white hats they see). If you do know the outcomes, you only need to predict the response of any one prisoner behind you.

If P(n) is the probability of your correctly predicting the response of Prisoner #n, given what they have heard and what they see, and if you are prisoner N, then the probability of your survival is (at least) P(N-1) for the no-outcomes-information case, and Max(P(1), P(2), ... , P(N-1)) for the other case (assuming you know which one is highest).

Title: Re: single file execution (want hint)
Post by rmsgrey on Aug 28^th, 2003, 7:25am

on 08/20/03 at 16:24:05, Icarus wrote:

If P(n) is the probability of your correctly predicting the response of Prisoner #n, given what they have heard and what they see, and if you are prisoner N, then the probability of your survival is (at least) P(N-1) for the no-outcomes-information case, and Max(P(1), P(2), ... , P(N-1)) for the other case (assuming you know which one is highest).

That was my first thought, but then I spotted that, in some cases, you're better off taking the combined evidence of everyone else than just basing your answer on one person - for instance if you have P(5)=.9 and P(1...4)=.89 and people 1-4 all give you the same optimum choice while 5's information suggests the opposite, you're clearly better off going with the majority and assuming you guessed wrong with number 5.

I haven't actually done the maths to see whether this simplifies, or if, in general, James' equations have to be solved for each case to determine your survival chances.

Title: Re: single file execution (want hint)
Post by James Fingas on Aug 28^th, 2003, 8:37am

on 08/28/03 at 07:25:32, rmsgrey wrote:

That's what I was thinking of when I developed my formula. Hopefully it would suggest you go with the majority, as common sense predicts.

In fact, if things were this one-sided, then you'd be quite certain (p=.998 I think) that this was the correct decision.

But the beauty of the formula is that it allows you to get information when you know only a little about each person, and also when you think people will guess the opposite (paranoid delusional people). For instance, you might have probabilities in the 0.6 - 0.8 range, which would be difficult to weigh without doing a rigorous calculation.

For me, the most interesting thing about the formula is that it works even if the first person guessing doesn't know about the scheme. You just have to convince the other people that he does, (this might be a good opportunity to assess their probabilities).

I'm still thinking about the case where everybody knows that he first person doesn't know about the scheme, and how that might affect other people's strategy.