While traveling in the Kingdom of Arbitraria, you are accused of a heinous crime. Arbitraria decides whoâ€™s guilty or innocent not through a court system, but a board game. Itâ€™s played on a simple board: a track with sequential spaces numbered from 0 to 1,000. The zero space is marked â€śstart,â€ť and your token is placed on it. You are handed a fair six-sided die and three coins. You are allowed to place the coins on three different (nonzero) spaces. Once placed, the coins may not be moved.

After placing the three coins, you roll the die and move your token forward the appropriate number of spaces. If, after moving the token, it lands on a space with a coin on it, you are freed. If not, you roll again and continue moving forward. If your token passes all three coins without landing on one, you are executed. On which three spaces should you place the coins to maximize your chances of survival?

Extra credit: Suppose thereâ€™s an additional rule that you cannot place the coins on adjacent spaces. What is the ideal placement now? What about the worst squares â€” where should you place your coins if youâ€™re making a play for martyrdom?

Let’s suppose the track has length $N=1000$ (this will turn out not to matter!). We will begin by solving the simpler problem where we only get to place a single coin, and then we’ll solve the versions for two coins, three coins, etc.

### One coin

Let’s call $p_k$ the probability that we will survive if the coin is placed on space $k$. In other words, $p_k$ is the probability that we land on the space labeled $k$. Clearly $p_1 = \tfrac{1}{6}$, but it gets more complicated for larger $k$. The key is to realize that we can compute $p_k$ *recursively*. For example, to compute some $p_k$, note that if our first roll is a one, we must now roll a total $k-1$ with our remaining rolls in order to survive. If our first roll is a two, we must roll a total of $k-2$ with our remaining rolls, and so on. So we conclude that:

\[

p_k = \frac{1}{6}\left( p_{k-1}+p_{k-2}+\dots+p_{k-6} \right)

\]This holds for all $k$, actually, so long as we choose our initial conditions appropriately. We know that $p_1 = \tfrac{1}{6}$, so we can achieve the desired recurrence by choosing:

\[

p_0 = 1,\quad\text{and}\quad p_{k} = 0\text{ for }k<0
\]So now we have a simple recursive way of computing all the $p_k$. In fact, we are dealing with a linear recurrence relation with constant coefficients, so we can find a formula for $p_k$ using the characteristic polynomial. The result turns out to be:

\[

p_k = \frac{1}{7}\left( 2 + \eta_1^k + \eta_2^k + \bar{\eta}_2^k + \eta_3^k + \bar{\eta}_3^k \right)

\]where $\eta_1\approx -0.670332$, $\eta_2\approx -0.375695 + 0.570175i$, and $\eta_3\approx 0.294195 + 0.668367i$. Here, $\bar{\eta}$ denotes the complex conjugate of $\eta$. Unfortunately we can’t find an exact expression because the characteristic polynomial is sixth-order, and even if we factor out the trivial root at 1, we are left with a quintic, which will not have a closed-form solution in general. Nevertheless, this formula tells us that the probability of landing on a coin placed very far away is $p_\infty = \frac{2}{7}$, Neat!

Ok, back to business. The formula for $p_k$ isn’t all that useful, but we still have an efficient way of computing $p_k$ exactly via the recursion. Here is a plot of what $p_k$ looks like:

Notice that in the limit, we approach $\tfrac{2}{7} \approx 0.285714$, as expected. We can read off the coin locations that either maximize survival, or minimize it (martyrdom). The results are shown in the table below.

Deadly Game with one coin |
**Optimal coin location** |
**Exact survival probability** |
**Approximate probability** |

**Martyrdom** |
1 |
$\frac{1}{6}$ |
0.166667 |

**Survival** |
6 |
$\frac{16807}{46656}$ |
0.360232 |

### Two coins

Since the one-coin problem was difficult in the sense that we had to resort to computing all the probabilities and then picking the largest and smallest one, we can’t expect the two-coin problem to be any easier. That being said, we can leverage the work we’ve already done. Let’s call $q_{k,m}$ the probability that we will survive if the coins are placed on $k$ and $m$. We can compute $q$ by using the inclusion-exclusion principle. Namely,

\begin{align}

&P(\text{land on } k \text{ or } m) \\

&\qquad\qquad= P(\text{land on }k)+P(\text{land on }m)-P(\text{land on }k \text{ and } m)

\end{align}Landing on $k$ and $m$ requires landing on $k$ first (assuming $k\le m$) and then landing on $m$ given that we are on $k$. This is simply $p_{m-k}$. So in summary, if $k\le m$, we have:

\[

q_{k,m} = p_k+p_m-p_k p_{m-k}

\]Computing the $q$ values for each pair $(k,m)$, we can visualize the probabilities in 3D:

The landscape is even more complicated than before. The diagonal (corresponding to $k=m$) is sunken because this is when both coins are placed on the same square (much lower probability of survival!). The results are in the table below:

Deadly Game with two coins |
**Optimal coin locations** |
**Exact survival probability** |
**Approximate probability** |

**Martyrdom** |
1, 2 |
$\frac{1}{3}$ |
0.333333 |

**Survival** |
5, 6 |
$\frac{2401}{3888}$ |
0.617541 |

If we forbid adjacent coins, we obtain:

**Martyrdom** |
1, 7 |
$\frac{16807}{46656}$ |
0.360232 |

**Survival** |
4, 6 |
$\frac{4459}{7776}$ |
0.573431 |

### Three coins

This case is similar to the two-coin case, except that the solution space is now three-dimensional and therefore much more difficult to visualize. If we let $r_{k,m,n}$ be the probability that we will survive if the coins are placed on $k$, $m$, and $n$, and we assume that $k\le m \le n$, we can compute the probability using inclusion-exclusion once more:

\[

r_{k,m,n} = p_k+p_m+p_n-p_kp_{m-k}-p_kp_{n-k}-p_mp_{n-m}+p_kp_{m-k}p_{n-m}

\]The results for this case are given in the table below.

Deadly Game with three coins |
**Optimal coin locations** |
**Exact survival probability** |
**Approximate probability** |

**Martyrdom** |
1, 2, 7 |
$\frac{3697}{7776}$ |
0.475437 |

**Survival** |
4, 5, 6 |
$\frac{343}{432}$ |
0.793981 |

If we forbid adjacent coins, we obtain:

**Martyrdom** |
1, 3, 7 |
$\frac{3913}{7776}$ |
0.503215 |

**Survival** |
6, 8, 10 |
$\frac{1198777}{1679616}$ |
0.713721 |

Note that it’s never in our best interest to place coins far apart from one another. All the “interesting” behavior (very large or very small probabilities) happens near the start. Take the three-coin case for example; if we place the coins far from the start and far from each other, each will get landed on with probability $\tfrac{2}{7}$ and they will be roughly independent. This means that:

\[

\textrm{P(survival)} \approx 1-(1-\tfrac{2}{7})^3 \approx 0.635569

\]and this places us squarely between the martyrdom and survival probabilities found in the table above. In other words, there is never any benefit to spreading out the coins, regardless of whether we are trying to win or lose… The $N=1000$ is a red herring!

Nice solution as usual!

Minor issue: your characteristic-polynomial formula for p_k is missing a term with the kth power of the fifth root, -0.67032.

Also, I prefer the following explanation of the recursion relation: if space k is the last stop, then p_k follows from the probabilities to have reached the next-to-last stop, which must be one of spaces k-6 through k-1. From any one of these, the probability to reach space k is 1/6. So it must be that p_k = (1/6)(p_(k-6)+…+p_(k-1)). We start at space zero with probability one, so p_0=1, and there are no negative spaces, so p_k=0 for k<0.

One more minor comment: at large k, p_k should be the reciprocal of the average roll; this is (1+2+3+4+5+6)/6 = 7/2, which agrees with what you got from the recursion relation.

Thanks for the comments! I added the missing root. Nice interpretation of 2/7 also, hadn’t thought of it that way.

Wouldn’t the solution for 3 coins be 5, 6, 12 because, as your own graph shows, 12 is the third-highest probability space? You have a lower chance of landing on 4 than on 12.

Similarly, for nonadjacent spaces, you would just read off the three highest non-adjacent values on the graph. They look to be 6, 12, 14 to me, but it’s hard to tell because the graph is small.

Similarly, for martyrdom you’d take the lowest values: 1, 2, 3 (and 1, 3, 7 if non-adjacent). Or am I missing something?

The $p_k$ probabilities (probability that you’ll land on $k$) that I plotted in my first figure are

notadditive. For example, the probability that you land on 1, 2, or 3 is 50%, since it happens precisely when you roll a 1, 2, or 3 on your first roll. However, if you add $p_1+p_2+p_3$, you actually get 58.78%.The reason why you end up with a higher number is that by just adding the probabilities, you’re double-counting some of the events. For example, the probability that you land on 3 also accounts for the case where you landed on a 1 first and then rolled a 2. Using the inclusion-exclusion principle as I explained avoids double-counting.

The lowest probability you can get is actually to choose 1, 2, 7, which gives a probability of survival of 47.5%; lower than the 50% you get by picking 1, 2, 3.

With the help of a computer, here are the answers for 4 and 5 and 6 coins. Each probability is execution probability.

4 coins

best 3,4,5,6 0.0926 worst 1,2,3,7 0.4020

nonadjacent: best 4,6,8,11 0.1889 worst 1,3,7,13 0.3734

5 coins

best 2,3,4,5,6 0.0278 worst 1,2,3,7,8 0.3040

nonadjacent: best 4,6,9,11,13 0.1199 worst 1,3,7,13,19 0.2779

6 coins

best 1,2,3,4,5,6 0.0 worst 1,2,3,7,8,13 0.2359

nonadjacent: best 4,6,8,11,13,15 0.0762 worst 1,3,7,13,19,25 0.2064

Note that there are some periodic patterns; I do not know whether the problem for n coins has a closed form solution.

neat — one obvious thing I didn’t think of when I wrote up my solution is that the problem should be solvable recursively as you add more coins by just performing a new O(n) search. Makes sense that the best k coins should be a subset of the best k+1 coins, and similarly for the worst k coins. I don’t know why I didn’t think of that!

Nice solution! How do you normalise the probabilities?

Wouldn’t that lead to the incorrect answer of 4,6,8 for the case of non-adjacent survival?

I’m not sure I understand your question.

I’m suggesting the following iterative approach: first find $k$ to maximize $p_k$, call the optimal index $k_1$. Then, find $k$ to maximize $q_{k_1,k}$, call the optimal index $k_2$. And finally find $k$ to maximize $r_{k_1,k_2,k}$.

What I did in my solution was to search over all $(k_1,k_2,k_3)$ to maximize $r_{k_1,k_2,k_3}$ directly. My approach is $O(N^3)$ whereas the iterative approach is $O(3N)$ instead.

Right, I think I’m following you on all that. My point is that if you used the iterative approach for the question of how to maximize chance of survival with coins on three non-adjacent spaces you would have gotten k1 = 6, k2 = 4, and k3 = 8, which is not the correct answer.

@Hector Pefo — oh wow you’re absolutely right. What a fiendish problem!

Hello Laurent,

thank you for this post, it is great.

I agree that the right answer is to place the coins on 456. I am getting a slightly different answer than you for the survival chance. I got the same answers as you for the 1 and 2 coin cases, but now on 3 coins, I’m at around .801333. I’ve been puzzling on this for a bit and looked at your formula, which I think is:

R456 = p4 + p5 + p6 â€“ p4*p1 â€“ p4*p2 â€“ p5*p1 + p4*p1*p1

my way of looking at it was slightly different:

define p5~4, the prob of getting 5 without first getting 4 as,

p5~4= p5 – p4/6 = 343/1296 (same as p4)

define p6~5~4, the prob of getting 6 without first getting 4 or 5 as,

p6~5~4 = p6 – (p5~4)/6 – p4/6 = 12,691/46,656

— Rather than using p1 and p2 in the formula, I’m dividing by 6 to eliminate hitting 5 (that wasn’t previously a 4) and then rolling a 1, or hitting 4 and then rolling a 2.

I think the difference between our answers is in the “p4 followed by 2” term in my p6~5~4, because I use -p4/6, the likelihood of throwing a 2 after getting 4, rather than your -p4*p2. that’s because I don’t want to eliminate the chance of hitting 4 then throwing a 1 and a 1, as I already eliminated 4 followed by 1 previously in defining p5~4.

so I wind up with

R456 = p4 +p5~4 + p6~5~4 = 37,387/46,656, which is around .801333

am I making an error?

thanks,

David

I think you DO want to eliminate the case where you roll a 4 then 1, 1, i.e. the case where you land on (4,5,6). In the formula you gave:

p6~5~4 = p6 – p5~4/6 – p4/6

If we just take a look at whether you land on 4, 5, or 6, then:

p6 includes the four cases: (~4,~5,6) (4,5,6) (4,~5,6) (~4,5,6)

p5~4/6, i.e. rolling a 1 after 5~4, is the case (~4,5,6)

finally, p4/6, i.e. rolling a 2 after a 4, is the case (4,~5,6).

The thing we’re trying to calculate is p6~5~4, which is just (~4,~5,6).

So by just writing p6~5~4 = p6 – p5~4/6 – p4/6, you’re not actually eliminating the (4,5,6) possibility.

By just enumerating the possible ways of achieving p4, p5~4, and p6~5~4, it’s not difficult to see that the probabilities should actually be the same for all three. One way to see this is to notice that p4 can occur in 8 ways:

(4) (13) (22) (31) (112) (121) (211) (1111)

The probability of this is $\frac{1}{6} + 3\frac{1}{6^2} + 3\frac{1}{6^3} + \frac{1}{6^4} = \frac{343}{1296}$, same as what you found.

Now p5~4 can also occur in 8 ways. Just take each sequence that yielded p4, and add 1 to the last roll! i.e.

(5) (14) (23) (32) (114) (122) (212) (1112)

The probability of this is the same as p4. Similarly, the ways of achieving p6~5~4 are found by again adding 1 to the last roll:

(6) (15) (24) (33) (115) (123) (213) (1114)

So clearly the probability should be the same again.

thank you Laurent.

before writing to you I actually convinced myself 3 times that 343/432 was right. and each time I went back and said, ‘hang on a sec’ and looked again. and of course the elegance of p(4), p(5~4) and p(6~5~4) all being equal was so powerful. but I just had this blind spot that wouldn’t go away.

I kept saying, well I’ve disallowed 4 followed by 1 and 5~4 followed by 1, so 4 followed by 1 and 1 is already disallowed. but it’s not because it is in the p(6) prob of 7^5/6^6 we’re backing out of. I was reading left to right, but really it has to be right to left -in other words, “we’re at 6, how could we have gotten here?”

and what was really beautiful was your demo that 4, 5~4, and 6~5~4 are all formed by basically the same sequences.

thanks again for taking the time on this.

Best,

David