Consider the following board with a pawn in position $4$:

enter image description here

The game works by rolling a dice and going forward the number of positions as marked in the dice. So for example if you roll $1$ you go from position $4$ to position five. If you roll $2$ you get to the finish and the game ends. If you roll three however you end up at position $5$, because if you pass the finish you start going back.

However you can roll more than once. So for example, rolling a three and then a one will take you from position $4$ to position $5$ and then to the finish.

The question is how many different ways are there to get to the finish in $k$ or less steps (where one step consists in rolling one dice and moving the pawn the appropriate number of tiles).

  • $\begingroup$ This is a classic Markov chain. $\endgroup$ – Thomas Andrews Feb 11 '15 at 4:37

Each time, there is exactly one roll that will let you finish. So there is one way to finish in one roll, $5\cdot 1$ to finish in two rolls (because you need not to finish the first time), and generally $5^{(n-1)}$ ways to finish in exactly $n$ rolls. For $k$ or less, we add up the geometric series, getting $\frac {5^k-1}{5-1}$


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.