{"id":1416,"date":"2016-10-15T10:36:48","date_gmt":"2016-10-15T15:36:48","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=1416"},"modified":"2016-10-17T13:49:55","modified_gmt":"2016-10-17T18:49:55","slug":"the-deadly-board-game","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/the-deadly-board-game\/","title":{"rendered":"The deadly board game"},"content":{"rendered":"

This Riddler classic puzzle<\/a> involves a combination of decision-making and probability.<\/p>\n

\nWhile traveling in the Kingdom of Arbitraria, you are accused of a heinous crime. Arbitraria decides who\u2019s guilty or innocent not through a court system, but a board game. It\u2019s played on a simple board: a track with sequential spaces numbered from 0 to 1,000. The zero space is marked \u201cstart,\u201d 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.<\/p>\n

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?<\/p>\n

Extra credit: Suppose there\u2019s an additional rule that you cannot place the coins on adjacent spaces. What is the ideal placement now? What about the worst squares \u2014 where should you place your coins if you\u2019re making a play for martyrdom?\n<\/p><\/blockquote>\n

Here is my solution:
\n[Show Solution]<\/a><\/p>\n

\n

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.<\/p>\n

One coin<\/h3>\n

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<\/em>. 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:
\n\\[
\np_k = \\frac{1}{6}\\left( p_{k-1}+p_{k-2}+\\dots+p_{k-6} \\right)
\n\\]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:
\n\\[
\np_0 = 1,\\quad\\text{and}\\quad p_{k} = 0\\text{ for }k<0\n\\]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<\/a>, so we can find a formula for $p_k$ using the characteristic polynomial. The result turns out to be:
\n\\[
\np_k = \\frac{1}{7}\\left( 2 + \\eta_1^k + \\eta_2^k + \\bar{\\eta}_2^k + \\eta_3^k + \\bar{\\eta}_3^k \\right)
\n\\]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<\/a>. Nevertheless, this formula tells us that the probability of landing on a coin placed very far away is $p_\\infty = \\frac{2}{7}$, Neat!<\/p>\n

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:<\/p>\n

\"deadly_game_1\"<\/a>
\nNotice 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.<\/p>\n\n\n\n\n
Deadly Game with one coin<\/td>\nOptimal coin location<\/b><\/td>\nExact survival probability<\/b><\/td>\nApproximate probability<\/b><\/td>\n<\/tr>\n
Martyrdom<\/b><\/td>\n1<\/td>\n$\\frac{1}{6}$<\/td>\n0.166667<\/td>\n<\/tr>\n
Survival<\/b><\/td>\n6<\/td>\n$\\frac{16807}{46656}$<\/td>\n0.360232<\/td>\n<\/tr>\n<\/table>\n

Two coins<\/h3>\n

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<\/a>. Namely,
\n\\begin{align}
\n&P(\\text{land on } k \\text{ or } m) \\\\
\n&\\qquad\\qquad= P(\\text{land on }k)+P(\\text{land on }m)-P(\\text{land on }k \\text{ and } m)
\n\\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:
\n\\[
\nq_{k,m} = p_k+p_m-p_k p_{m-k}
\n\\]Computing the $q$ values for each pair $(k,m)$, we can visualize the probabilities in 3D:<\/p>\n

\"deadly_game_2\"<\/a>
\nThe 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:<\/p>\n\n\n\n\n
Deadly Game with two coins<\/td>\nOptimal coin locations<\/b><\/td>\nExact survival probability<\/b><\/td>\nApproximate probability<\/b><\/td>\n<\/tr>\n
Martyrdom<\/b><\/td>\n1, 2<\/td>\n$\\frac{1}{3}$<\/td>\n0.333333<\/td>\n<\/tr>\n
Survival<\/b><\/td>\n5, 6<\/td>\n$\\frac{2401}{3888}$<\/td>\n0.617541<\/td>\n<\/tr>\n<\/table>\n

If we forbid adjacent coins, we obtain:<\/p>\n\n\n\n
Martyrdom<\/b><\/td>\n1, 7<\/td>\n$\\frac{16807}{46656}$<\/td>\n0.360232<\/td>\n<\/tr>\n
Survival<\/b><\/td>\n4, 6<\/td>\n$\\frac{4459}{7776}$<\/td>\n0.573431<\/td>\n<\/tr>\n<\/table>\n

Three coins<\/h3>\n

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:
\n\\[
\nr_{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}
\n\\]The results for this case are given in the table below.<\/p>\n\n\n\n\n
Deadly Game with three coins<\/td>\nOptimal coin locations<\/b><\/td>\nExact survival probability<\/b><\/td>\nApproximate probability<\/b><\/td>\n<\/tr>\n
Martyrdom<\/b><\/td>\n1, 2, 7<\/td>\n$\\frac{3697}{7776}$<\/td>\n0.475437<\/td>\n<\/tr>\n
Survival<\/b><\/td>\n4, 5, 6<\/td>\n$\\frac{343}{432}$<\/td>\n0.793981<\/td>\n<\/tr>\n<\/table>\n

If we forbid adjacent coins, we obtain:<\/p>\n\n\n\n
Martyrdom<\/b><\/td>\n1, 3, 7<\/td>\n$\\frac{3913}{7776}$<\/td>\n0.503215<\/td>\n<\/tr>\n
Survival<\/b><\/td>\n6, 8, 10<\/td>\n$\\frac{1198777}{1679616}$<\/td>\n0.713721<\/td>\n<\/tr>\n<\/table>\n

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:
\n\\[
\n\\textrm{P(survival)} \\approx 1-(1-\\tfrac{2}{7})^3 \\approx 0.635569
\n\\]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!<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

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\u2019s guilty or innocent not through a court system, but a board game. It\u2019s played on a simple board: a track with sequential spaces numbered from 0 to … Continue reading “The deadly board game”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":1440,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[8,21,15,2],"class_list":["post-1416","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-probability","tag-random-walk","tag-recursion","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1416","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=1416"}],"version-history":[{"count":39,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1416\/revisions"}],"predecessor-version":[{"id":1458,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1416\/revisions\/1458"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/1440"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=1416"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=1416"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=1416"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}