22
$\begingroup$

You are playing a game with dice. You have a grid with 13 cells shown below. A token starts in the left-most cell (start). Each turn you roll an $n$-sided die and get a number $x$ between $1$ and $n$, inclusive. If you can move the token $x$ cells to the right without going outside the grid then you make that move; otherwise you keep the token in its current cell (do nothing). The game terminates when you reach the right-most cell (end). Before the game starts you can choose an $n$-sided die to play with, where $n$ ranges from $2$ to $12$, inclusive. Which $n$-sided die should you choose to finish the game as fast as possible (in expectation) ?

enter image description here

$\endgroup$
7
  • $\begingroup$ √n rounded up gives a good approximation $\endgroup$
    – Bohemian
    Apr 18 at 23:23
  • $\begingroup$ @Bohemian what does it approximate? $\endgroup$ Apr 19 at 5:23
  • $\begingroup$ It approximates the answer, what else. √12 rounded up is 4, which is the same as the accepted answer. Intuitively it feels right too, to me anyway. $\endgroup$
    – Bohemian
    Apr 19 at 5:55
  • $\begingroup$ I wrote a program to check your approximation. It is a good approximation, but doesn't always work. See the results here: pastebin.com/7NZ79vh1 $\endgroup$ Apr 19 at 7:37
  • $\begingroup$ It looks to me like it always works! I only claimed an approximation. $\endgroup$
    – Bohemian
    Apr 19 at 7:40
14
$\begingroup$

Here is a relatively quick way to get an approximate answer.

Let $k$ be the number of steps to the end (in this case $12$), and $n$ the number of sides on the die.

First you need to look at the end game.

Once you land in the last $n$ squares, there will always be one value that finishes the game. This means that the expected number of throws until you get a winning value is $n$. It makes no difference that you sometimes move closer, and that the value of the winning throw changes accordingly, the expected value of the number of throws until you get the winning one does not change.

Now to estimate the number of throws until we reach the end game:

The expected value of a throw is $\frac{n+1}2$, so that is the average number of steps you take per throw. You need to go $k-n$ steps till the end game, so this takes $$\frac{2(k-n)}{n+1} = 2\frac{k+1-n-1}{n+1} = \frac{2(k+1)}{n+1} -2$$

We need to minimise this.

The approximation of the expected total number of throws is: $$f(n) = \frac{2(k+1)}{n+1} +n-2$$ Set the derivative to zero to find the value of $n$ where it is minimal: $$f'(n) = -\frac{2(k+1)}{(n+1)^2} +1 = 0$$ $$(n+1)^2 =2(k+1)$$ $$n =\sqrt{2(k+1)}-1$$ For $k=12$ we get $n=4.099$. This is closest to $n=4$, so most likely the best size die is $4$, but to be absolutely sure we would have to calculate the expected number of throws more exactly for $n\in\{3,4,5\}$.

$\endgroup$
6
  • $\begingroup$ This is a great answer without any computer assistance. I wonder if we could possibly round your final result (to the nearest integer) and get the final answer that way? $\endgroup$ Apr 15 at 11:47
  • 1
    $\begingroup$ Because $f(n)$ is convex for fixed $k$ and positive $n$, the integer minimum is obtained by rounding the continuous minimum up or down (not necessarily to the closest integer). So for $k=12$, you need only check $\{4,5\}$. $\endgroup$
    – RobPratt
    Apr 15 at 12:58
  • $\begingroup$ @RobPratt That is true if $f(n)$ were exact for integer $n$. Unfortunately for $n=3,4,5$ the function $f(n)$ takes the values $7.5$, $7.2$, $7.333$, while the real expected values are $7.832$, $7.596$, $7.786$. This function is only an approximation. $\endgroup$ Apr 15 at 13:44
  • $\begingroup$ Well, going back into the lore a bit more, there cannot be a 3-sided die, and 5-sided die are not so common (I found this discussion, but I don't know if it is actually possible to create one). So only the 4-sided die remains ;) $\endgroup$
    – frarugi87
    Apr 16 at 9:04
  • $\begingroup$ @frarugi87 Maybe it would be more accurate to say 3-valued die so that you can allow a cube with each value repeated twice. Actually, die means cube so if taken literally there cannot be any other shapes, and you take it more figuratively than you can also allow n-sided tops. $\endgroup$ Apr 16 at 9:24
10
$\begingroup$

With a little more work than Jaap's very nice approximate answer we can explicitly calculate the values we need. Pick a die -- say it has $n$ sides -- and let $a_j$ be the expected number of turns when you are $j$ spaces away from winning. Obviously $a_0=0$, and Jaap's insight about how the game ends shows that $a_j=1/n$ when $1\leq j\leq n$. After that we have $a_j=1+\frac{a_{j-1}+\cdots+a_{j-n}}n$. The most efficient way to proceed at this point is just to roll up our sleeves and calculate (especially as computers make this pretty painless), but let's try to do it with brains instead. (Spoiler alert: we fail, or at least I do.)

There's some standard mathematical technology for solving linear recurrences like this without that "inhomogeneous" $1+$ term, and we can reduce this case to that one by applying the recurrence for $j$ and for $j+1$ and subtracting. $a_{j+1}=1+\frac{a_{j}+\cdots+a_{j-n-1}}n$ so $a_{j+1}-a_j=(a_j-a_{j-n})/n$ or $na_{j+1}-(n+1)a_j+a_{j-n}=0$. This means that we need to consider the roots of the equation $nX^{n+1}-(n+1)X^n+1=0$; there are $n+1$ of them, which we may call $x_0,\ldots,x_n$; for any sequence $(a_j)$ satisfying the recurrence we have $a_j=c_0x_0^j+\cdots+c_nx_n^j$; in principle we can now find the coefficients $c$ by looking at the first $n+1$ values $0,n,n,\ldots,n$ and solving the resulting system of $n+1$ linear equations. Unfortunately, although we can easily see that $x_0=1$ is one root, we don't have an explicit form for the others, and even in e.g. the smallish special case $n=4$ the answer is going to be some horrific thing involving the roots of a quartic equation and I don't see any way to simplify it.

So, calculation it is. I agree with Jaap that we only really need to look at $n=3,4,5$, but the calculations are tedious enough that I enlisted a computer to do them, and at that point we might as well try all the permitted $n$.

It turns out that

the best is indeed $n=4$ with an expected 124461/16384=7.5965ish turns to win; $n=3$ is close but worse, at 51388/6561=7.8323ish; likewise $n=5$ at 121656/15625=7.7860ish.

$\endgroup$
8
  • 1
    $\begingroup$ Nice work. However, I think your final answers are for 11 steps rather than 12. I used a spreadsheet and got 7.8323, 7.5965, 7.78598 for n=3,4,5 at 12 steps. $\endgroup$ Apr 15 at 11:48
  • $\begingroup$ @JaapScherphuis my values agree with yours. $\endgroup$ Apr 15 at 11:49
  • 2
    $\begingroup$ @DmitryKamenetsky Of course they do. With n=12 you are immediately in the end game, with an expected number of throws of 12. With n=11 any first throw brings you into the end game with an expected number of further throws of 11. $\endgroup$ Apr 15 at 11:54
  • 1
    $\begingroup$ Cool, I've learned something from my own puzzle :) $\endgroup$ Apr 15 at 11:55
  • 1
    $\begingroup$ Ugh, yes. The fractions are correct, the decimal approximations are not. Will fix. [EDITED to add:] Now fixed. $\endgroup$
    – Gareth McCaughan
    Apr 15 at 13:09
7
$\begingroup$

Simulating in C# / LINQPad:

void Main()
{
    testIt();
}

Random rnd = new Random();
// Define other methods and classes here
void testIt()
{
    var tries = new List<List<int>>();
    for (int n = 2; n <= 12; ++n)
    {
        var dieTries = new List<int>();
        tries.Add(dieTries);

        for (var t = 0; t < 500000; ++t)
        {
            dieTries.Add(oneTry(n));
        }
    }
    tries.Select((x, nn) => new { t=nn+2, a = x.Average()}).Dump();
}

int oneTry(int n) {
    int pos = 0;
    int rolls = 0;
    while (pos != 12) {
        int roll = rnd.Next(1,n+1);
        if (pos+roll <= 12) {
            pos += roll;
        }
        ++rolls;
    }
    return rolls;
}

I'm also getting $n=4$ as the best die to choose.

n   rolls
-------------
2   8.8892764 
3   7.8335088 
4   7.595364 
5   7.7869668 
6   8.1597884 
7   8.706521 
8   9.4254922 
9  10.2330226 
10 11.1029222 
11 11.993705 
12 11.9961702 

```
$\endgroup$
9
  • 1
    $\begingroup$ +1 for including a 2-sided die as an option. :) $\endgroup$
    – bob
    Apr 15 at 19:11
  • 1
    $\begingroup$ A 2-sided die is just a coin :) $\endgroup$ Apr 16 at 1:41
  • 2
    $\begingroup$ @ZizyArcher Oh really? $\endgroup$ Apr 16 at 13:06
  • 3
    $\begingroup$ As Ross Presser points out, while a 3-side polyhedral die doesn't exist, there's nothing that says it has to be polyhedral; you can have curved surfaces. You can even have a 1-sided die, though it's kind of pointless. :) $\endgroup$
    – bob
    Apr 16 at 14:38
  • 2
    $\begingroup$ @bob Additional nitpicking: even totally flat-sided polyhedra (though not regular) can serve as 3 sided dice. For example, making the cupolas on an elongated triangular bipyramid so pointy that the die will never rest on them. (see the 3D model in particular) $\endgroup$ Apr 16 at 15:49
1
$\begingroup$

It's easy to calculate an exact numerical solution (up to the accuracy of the numerical calculations used, at least) without simulation using dynamic programming.

In particular, using the observation in Jaap Scherphuis' answer that the expected number of rolls to reach the goal using an $n$-sided die from any of the last $n$ squares is $n$, we can define a recurrence for the expected number of rolls to reach the goal from the $k$-th last square before the goal:

$$ e_k = \begin{cases} n & \text{if } 1 \le k \le n, \\ 1 + \frac1n \sum_{i=1}^n e_{k-i} & \text{if } k > n. \end{cases} $$

Note that each value of the sequence $\langle e_k \rangle$ after the $n$-th depends only on (the sum of) the $n$ previous values.

Thus we can compute the values of the sequence iteratively up to any desired index simply by initializing the first $n$ values to $n$ and then looping over the remaining indexes from $n+1$ upwards, setting the value of the $k$-th element to one plus the average (i.e. the sum divided by $n$) of the $n$ previous elements. As long as we store all the previously calculated expectation values (or at least the last $n$ of them) in a list, computing the sum will be easy and fast.

Here's a simple Python program that does this:

target = 12
for n in range(2, target+1):
  expectation = [n] * n
  while len(expectation) < target:
    expectation.append(1 + 1/n * sum(expectation[-n:]))
  print(f"Expected number of d{n} rolls to reach {target} = {expectation[-1]}")

Running this program produces the following output:

Expected number of d2 rolls to reach 12 = 8.888671875
Expected number of d3 rolls to reach 12 = 7.832342630696538
Expected number of d4 rolls to reach 12 = 7.59649658203125
Expected number of d5 rolls to reach 12 = 7.785984000000001
Expected number of d6 rolls to reach 12 = 8.161394032921809
Expected number of d7 rolls to reach 12 = 8.705955851728445
Expected number of d8 rolls to reach 12 = 9.423828125
Expected number of d9 rolls to reach 12 = 10.234567901234568
Expected number of d10 rolls to reach 12 = 11.100000000000001
Expected number of d11 rolls to reach 12 = 12.0
Expected number of d12 rolls to reach 12 = 12

from which we can easily observe that the minimum indeed occurs for a four-sided die.

Note that the program above is far from perfect. For example, it could be optimized to only store the last $n$ elements of the sequence and also their sum, updating the sum in constant time after each iteration by subtracting the $n$-th previous element and adding the new element just calculated. Also, the code could fairly easily be changed to use exact rational numbers instead of approximate floating-point arithmetic, thus giving mathematically exact results. However, it's already more than efficient enough even without such optimizations, and already more than accurate enough for the optimum to be clear even from a floating-point calculation.

$\endgroup$
1
  • $\begingroup$ This is very nice. Thank you for sharing. $\endgroup$ Apr 19 at 2:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.