# Old childhood game

Well couple of days ago I saw my nephews playing a game that I played as a child (back then there was no computers and we had to play outside :)) And it got me thinking. Game revolves around coupple of simple rules and starts by throwing a rock on a $3$X$3$ square drawn on a sidewalk (filled with numbers $1-9$) Once the first player throws a rock and the rock falls on, let say number $2$ square that that player "moves" two steps forward and then decides how it will proceed to reach the "goal" which is $10$ steps from its starting point (I am simplifying the rules and objectives a bit). The decision is, he/she can then move by $2$ steps at the time to reach $10$ or $1$ step at the time or mix his/hers decisions but cannot go higher that $2$. However, once he/she decides to use lower number he/she cannot take the higher one again, so:

2+2+2+2+2+2 = 10
or
2+2+2+1+1+1+1 = 10
or
2+1+1+1+1+1+1+1+1 = 10


but not:

2+2+1+2+1+2 = 10 - no,no


Next, once the decision has been made and the player reaches $10$ (let say the $2+2+2+2+2+2$ = $10$ was the choice) all other players cannot make more than $6$ moves to reach the same goal ($10$) and the number of steps they start with has to be higher than $2$, so the next player throws a rock and gets $3$ thus his/hers options are:

3+2+2+2+1 =10 (5 moves)
3+3+3+1=10 (4 moves)
3+3+2+2+1=10 (6 moves)
...


also in each case player cannot move more than the initial number of steps he/she chose (got by throwing a rock if it got $3$ then $3$ steps is highest he/she can do per move) but can decide to change the numbers to $2$ or $1$ obeying the above rules (no going back)

After reflecting on the game I started wondering how many possible strategies there are in any given particular case and how would i compute that? So for numbers $3, 4, 5, 6, 7, 8$ and $9$ how many possible strategies there are in total?

Can anyone help with this ??

Thank you.

## 1 Answer

Generalizing to forming a number $N$ as a sum of a sequence of non-increasing numbers each not more that $V$, we have the following recurrence formula:

\begin{align*} f(x,y) = \begin{cases} 0 & (y < 0)\\ 1 & (y = 0)\\ \sum_{i=1}^{x} f(i,y-i) \end{cases} \end{align*}

Where $x$ represents the largest integer available at that point in time and $y$ is the remaining number of steps. Drawing the table of values in your case, we get:

|y / x|  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |
-------------------------------------------------------------
|  0  |  1  |  1  |  1  |  1  |  1  |  1  |  1  |  1  |  1  |
-------------------------------------------------------------
|  1  |  1  |  1  |  1  |  1  |  1  |  1  |  1  |  1  |  1  |
-------------------------------------------------------------
|  2  |  1  |  2  |  2  |  2  |  2  |  2  |  2  |  2  |  2  |
-------------------------------------------------------------
|  3  |  1  |  2  |  3  |  3  |  3  |  3  |  3  |  3  |  3  |
-------------------------------------------------------------
|  4  |  1  |  3  |  4  |  5  |  5  |  5  |  5  |  5  |  5  |
-------------------------------------------------------------
|  5  |  1  |  3  |  5  |  6  |  7  |  7  |  7  |  7  |  7  |
-------------------------------------------------------------
|  6  |  1  |  4  |  7  |  9  |  10 |  11 |  11 |  11 |  11 |
-------------------------------------------------------------
|  7  |  1  |  4  |  8  |  11 |  13 |  14 |  15 |  15 |  15 |
-------------------------------------------------------------
|  8  |  1  |  5  |  10 |  15 |  18 |  20 |  21 |  22 |  22 |
-------------------------------------------------------------
|  9  |  1  |  5  |  12 |  18 |  23 |  26 |  28 |  29 |  30 |
-------------------------------------------------------------
|  10 |  1  |  6  |  14 |  23 |  30 |  35 |  38 |  40 |  41 |
-------------------------------------------------------------


Then the total number of ways is the sum of the numbers on the bottom row, which is $1 + 6 + 14 + 23 + 30 + 35 + 38 + 40 + 41 = 228$

At the moment I am not sure if there is a closed form formula for $f(x,y)$.