9
$\begingroup$

2 criminals A and B, were recently captured and brought to prison. They were then locked in two separate rooms.

Known for being exceedingly smart, the prison warden set a test for them. They flip a fair coin an infinite number of times and told outcomes of odd trials to A and even trials to B.

Now A and B are separately told to pick a trial whose outcome they don't know, i.e., A is supposed to pick an even number, and B is supposed to pick an odd number. If the outcomes of the trials A and B picked are the same, the prison warden will release them. If they are different, they will spend life in jail.

The Warden told them what they were going to do and let them agree upon a common strategy in advance but after that they can't communicate.

Find a strategy such that the chance of winning is higher than $0.5$.

I recently tried this problem in university and I am interested to see other people's solutions, and perhaps the optimal solution.

Edit: My strategy is that both players agree that as soon as they see 2 tails in a row for themselves, they pick the number in the middle, i.e. A sees a tail on coin flip 2 and 4 so he picks 3, B does the same. After running this on a computer simulation I get a 60% winrate. Although I don't fully understand why.

Edit: a 70% chance of winning has been found on my Puzzling StackExchange duplicate post!

Strategies so Far

  1. 70% chance of winning by @Jaap Scherphuis
  2. 2/3 probability of winning by @Mike Earnest
  3. 62.5% chance of winning by @Teo Miklethun
$\endgroup$
8
  • $\begingroup$ What is your solution? $\endgroup$
    – saulspatz
    Commented Sep 11, 2021 at 16:51
  • $\begingroup$ @saulspatz I'm still working on optimizing my own solution, and I don't want to influence other answers yet. I will update my post at a later date. $\endgroup$
    – Igor
    Commented Sep 11, 2021 at 16:56
  • 1
    $\begingroup$ hello igor, do the prisoners guess simulatonsly? i.e can B see what A guesed or not? $\endgroup$ Commented Sep 11, 2021 at 17:10
  • 3
    $\begingroup$ For your interest: this is a variation of the "Levine Hat Puzzle". You may find some previous works on it by searching for it. $\endgroup$
    – WhatsUp
    Commented Sep 11, 2021 at 17:34
  • 1
    $\begingroup$ BTW, if you post this on Puzzling SE, there is a greater probability people will compete with each other to find the optimal strategy. $\endgroup$ Commented Sep 14, 2021 at 0:40

2 Answers 2

5
$\begingroup$

I can get a win probability of $2/3$. I have no clue if this is optimal.

Let me use a different numbering system for convenience. Say that player $A$ sees the flips $A_1,A_2,A_3,\dots,$ and player $B$ sees the flips $B_1,B_2,B_3,\dots$.

  • Player $A$ finds the smallest $i$ for which $A_i$ is heads, and points to $B_i$.

  • Player $B$ finds the smallest $j$ for which $B_j$ is heads, and points to $A_j$.

Let $p$ be the probability that $i=j$. In this case, they are guaranteed to win. If $i\neq j$, then the conditional probability of winning is exactly $\frac12$. Therefore, the overall probability of winning is $$ p+(1-p)\cdot \frac12=\frac12(p+1) $$ Since $$ p=\frac14+\frac1{4^2}+\frac1{4^3}+\dots=\frac{1}{3}, $$ the probability of winning is $2/3$.

To explain the above equation for $p$, we add up...

  • The probability both player's first instance of heads is on the first flip. This probability is $(1/2)\times (1/2)=1/4$.

  • The probability both players' first instance of heads in on the second flip. For this to happen, both sequences must start out with $T$, then $H$, so the probability is $(1/2\times 1/2)\times(1/2)\times (1/2)=(1/4)^2$.

  • In general, the probability of both players' first instance of heads occurring on the $k^{th}$ flip is $[(1/2)^k]^2$, since they both need to get the sequence $TT\cdots TH$, with $(k-1)$ $T$'s. Therefore, we need to sum up $(1/2)^{2k}$ from $k=1$ to $\infty$. This is exactly the sum I had before.

$\endgroup$
4
  • $\begingroup$ Interesting solution Mike! How exactly do you find the probability of $p$? $\endgroup$
    – Igor
    Commented Sep 13, 2021 at 2:28
  • $\begingroup$ @Igor I've added an explanation. $\endgroup$ Commented Sep 13, 2021 at 4:40
  • 1
    $\begingroup$ I've been thinking about it for a while a finally had my aha moment. I excitedly rushed back here to say I solved it, and I'm glad to see you wrote exactly what I was going to!! Thanks again Mike for your great answer and explanation. I wonder as well if this is optimal. $\endgroup$
    – Igor
    Commented Sep 13, 2021 at 5:02
  • $\begingroup$ @Igor Actually, I suspect it is suboptimal. I based this off of the basic strategy for the Levine's hat puzzle, from that paper linked in the comments. Their are fancier strategies in that paper, which I suspect could also be modified to work here. $\endgroup$ Commented Sep 13, 2021 at 14:43
5
$\begingroup$

Each person looks at the first flip they are allowed to see. If it's tails (represented by a 0), they pick the first flip they aren't allowed to see. Otherwise, if it's heads (represented by a 1), they pick the second flip they can't see.

You can draw out a table of possibilities to determine there is a 62.5% chance of winning with this strategy, but I'll describe the victory cases below anyways:

If A has "01" as their first two flips, and B has anything, then they'll win since A will pick the first flip from B, and B will pick "0" from A if B has a 0 as their first flip, and "1" if B has a 1 as their first flip. When examining the possible first 4 flips of the warden, the case above accounts for 4/16.

If B has "01", they win for the same reason, accounting for another 3/16 victory cases (since the "A:01 and B:01" case was counted above).

Moreover, since A and B's strategies are the same, if they get the same sequence of flips, they'll win. Again, this accounts for 3/16 new win cases (again the "A:01 and B:01" being the case that was already counted). These turn out to be the only ways to win with this strategy, leading to a (4+3+3)/16 = 62.5% > 50% chance of winning.

$\endgroup$
4
  • 2
    $\begingroup$ Wow, this is really smart! I checked it myself by just writing the solutions in terms of if A sees "00", "10", "01", "11" and filled in the possibilities of what B would choose and indeed there are 4, 2, 2, 2 cases respectively (total 10/16) where they pick the same number! Can you give me some intuition on how you came up with such a solution? $\endgroup$
    – Igor
    Commented Sep 11, 2021 at 17:59
  • 1
    $\begingroup$ Here is a Python implementation of this, with Monte Carlo estimation of the probability of winning. $\endgroup$
    – r.e.s.
    Commented Sep 12, 2021 at 16:21
  • $\begingroup$ @r.e.s. Nice code! But this is very easy to calculate by hand to be exactly 0.625. I was more wondering how he came up with such a strategy. $\endgroup$
    – Igor
    Commented Sep 12, 2021 at 16:43
  • 1
    $\begingroup$ @Igor I knew random choices wouldn't work, so the player's choices needed to depend on their own flips in some way. Having person A's choice be based on their first flip seemed like a pretty natural way to add something that wasn't random. Then I (pretty arbitrarily) thought about only the case where person A got a 0 as their first flip. In this case, the optimal strategy for person B happened to be the same strategy as I had chosen for person A. All that was left was to draw out the table and check that it actually worked. $\endgroup$ Commented Sep 12, 2021 at 18:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .