> Here is one for you (and that list): > > Tomorrow you and another prisoner are to be executed. But you will both be > spared if you can succeed in the following game. You and the other prisoner > have tonight to decide on a strategy for playing this game: Tomorrow you and > your fellow prisoner will be put in different rooms, and both of you will > observe two completely independent and separate sequences of 100 coin > tosses. The goal is for each of you to choose a position in the other > person’s sequence of coin tosses such that the results of the coin tosses in > those two selected positions match. (i.e., both heads or both tails). What > is your strategy? > > Example: > Sequence: 1 2 3 4 5 6 7 8 9 ... 100 > You see: T H H T T H H H T ... T and choose position 3 in your partner's > sequence > They see: H H T T H T T H T ... T and choose position 5 in your sequence > > You are both spared as you both chose matching results: both Tails.
A naive strategy (e.g. both choose randomly) gives them a probability of survival of .5. Also, attaining a probability of 1 is impossible: if it comes all heads on one side and all tails on the other, there is not possible match. This limit is still pretty close to 1, as the probability of this happening is (2 x 2^100)^-1. So the best we can do is improve the probability from .5. I found one improvement: Prisoner 1's strategy: If first head comes H, choose first position of the other sequence; If first head comes T, choose second position of the other sequence; Prisoner 2's strategy: Always choose first position of the other sequence, unless first two tosses come T H. In this case choose the second position of the other sequence. >From Prisoner 2's perspective, there are 4 options for the first two tosses: T T -> doesn't matter what P1 chooses, probability of survival is .5 H H -> doesn't matter what P1 chooses, probability of survival is .5 H T -> match becomes guaranteed, probability of survival is 1 T H -> choosing the first position on the other side would guarantee defeat, but choosing the second gives a probability of survival of .5 So this improves the probability of survival to .625. I suspect it is possible to do better, by using more bits of information from player 1's sequence to determine the choice. Possibly some generalization of the strategy I proposed... Cheers, Telmo. -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
