# Simple counting problem I invented (counting ways to end a board game)

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

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

• This is a classic Markov chain. – 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}$