0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.