The deadly board game

This Riddler classic puzzle involves a combination of decision-making and probability.

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?

Here is my solution:
[Show Solution]

17 thoughts on “The deadly board game”

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

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

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

    1. The $p_k$ probabilities (probability that you’ll land on $k$) that I plotted in my first figure are not additive. 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.

  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.

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

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

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

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

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *