4
$\begingroup$

In a board game, dice can roll either $1, 2, 3, 4, 5$ or $6$. The board has $N$ number of space. Every time of dice roll randomly, pawn moves forward exactly to dice rolled a number. Now the problem is how many possible ways or combination of jump can be possible to reach start to end point of a board? For an example end point is 100:

1+2+6+...+1 = 100 -> 1 way
1+3+1+...+3 = 100 -> 2 ways
...
i+i+....+i  =  100 -> N ways

Is there any algorithm of recursion?

$\endgroup$
  • $\begingroup$ This is equivalent to asking how many solutions there are to the equation $\sum_{i=1}^6 a_i i=N$ for $a_i \in \mathbb{N}_0$ (if we start at the zeroth square), if that somehow helps somebody solve this. $\endgroup$ – Bobson Dugnutt Aug 17 '16 at 14:30
6
$\begingroup$

Suppose in the beginning, the pawn is at position $0$ and the end position is $N$. Let $f(i)$ denote the number of ways to reach position $i$. Then the following relationships hold. $$ f(i) = \begin{cases} f(i-1) + f(i-2) + f(i-3) + f(i-4) + f(i-5) + f(i-6)\ &\text{if }\ i \geq 6 \\ f(4) + f(3) + f(2) + f(1) + f(0) &\text{if }\ i = 5\\ f(3) + f(2) + f(1) + f(0) &\text{if }\ i = 4\\ f(2) + f(1) + f(0) &\text{if }\ i = 3\\ f(1) + f(0) &\text{if }\ i = 2\\ f(0) &\text{if }\ i = 1\\ 1 &\text{if }\ i = 0 \end{cases} $$ The rationale is as follows. Without loss of generality, suppose $i \geq 6$. To reach $i$-th position, you can

  • first reach $(i-1)$-th position, and the result of dice roll is $1$;

  • first reach $(i-2)$-th position, and the result of dice roll is $2$;

  • $\cdots$

  • first reach $(i-6)$-th position, and the result of dice roll is $6$.


Algorithm. Given the relationships, it is easy to compute $f(N)$. Starting with $i = 1$, you compute $f(i)$ in increasing order of $i$ using the formulas above.

$\endgroup$
  • $\begingroup$ Thanks NP-hard. Would you please let me know in detail of the formula you given. As I am not so good in math, I need to learn it. $\endgroup$ – Iqbal Aug 19 '16 at 3:48
  • $\begingroup$ @Iqbal Enumerate all possible ways to reach the $i$-th position. There are six possibilities for the last but one position, namely, the $(i-6)$-th, the $(i-5)$-th, the $(i-4)$-th, the $(i-3)$-th, the $(i-2)$-th and the $(i-1)$-th positions. Therefore, $f(i)$ equals to "# of ways to reach the $i$-th position whose last but one position is $(i-6)$" plus "# of ways to reach the $i$-th position whose last but one position is $(i-5)$" plus $\cdots$ plus "# of ways to reach the $i$-th position whose last but one position is $(i-1)$". That is, $f(i) = f(i-6) + f(i-5) + \cdots + f(i-1)$. $\endgroup$ – PSPACEhard Aug 19 '16 at 4:33
  • $\begingroup$ NP-hard, I am sorry for taking a while to respond to your answer to my question here, but it's a good answer now that I have looked at it. Why did you delete it? $\endgroup$ – 6005 Aug 19 '16 at 18:27
  • 1
    $\begingroup$ @Yikai I understand from the formula you have ways to reach 100 = reach 99 + reach 98 + ... reach 94 but what about the extra case in which after reaching say 95 I still have 5 more places to go so the combination of that would be still 16 more ways to reach 100, am I missing something? likewise after reaching 99 I still have to reach 100 by rolling the dice one more time, so some value should get added to this sequence I suppose $\endgroup$ – Vihar Jun 20 '17 at 10:16
  • 1
    $\begingroup$ @Vihar It is not the number of combinations here. Note that to reach position $4$ from position $0$, the sequence $1$, $2$, $1$ is different from the sequence $2$, $1$, $1$. $\endgroup$ – PSPACEhard Jun 21 '17 at 2:18
1
$\begingroup$

the recursion is as follows, let $F_N$ be the number of ways to get with $N$ rolls, then we have:

$F_0=1$ and $F_k=0$ for $k<0$.

For $k>0$ we have $F_k=F_{k-1}+F_{k-2}+F_{k-3}+F_{k-4}+F_{k-5}+F_{k-6}$

Some c++ code:

#include <bits/stdc++.h>
using namespace std;

const int MAX=10010; //size of array
int F[MAX]; //stores results

int main(){
    F[0]=1;
    for(int i=1;i<MAX;i++){// we recursively fill the array
        for(int j=1; j<=6 && i-j>=0 ; j++){
            F[i]+=F[i-j];
        }
    }
    for(int i=0;i<10;i++) printf("%d\n",F[i]); // we print some values
}

The first ten values of $F_n$ starting with $F_0$:

0, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492

$\endgroup$
  • $\begingroup$ This is the pentanacci sequence (OEIS A001591). $\endgroup$ – Parcly Taxel Aug 17 '16 at 15:10
  • $\begingroup$ @Jorge, (C#) I got 0, 1, 2, 4, 8, 16, 32, 64, 127, 252, 500 ... why ? $\endgroup$ – Hassan Tareq Jun 11 '17 at 6:17
  • $\begingroup$ I know this is a bit old, but can you explain the ` F[i]+=F[i-j];` part a bit? I fail to comprehend the logic behind this line. $\endgroup$ – Tasos Anesiadis Jun 24 '18 at 13:48
  • $\begingroup$ sure, since we have the formula $F[i] = F[i-1] + .... + F[i-6]$ and all of the values of $F[i]$ are initialized as $0$ all we have to do is add $F[i-1]... F[i-6]$ to the initial value. $\endgroup$ – Jorge Fernández Hidalgo Jun 24 '18 at 14:04
  • $\begingroup$ Seems f(0) should also be 1, not 0. $\endgroup$ – Eric Wang Oct 10 '18 at 20:34
0
$\begingroup$

If I understand correctly the problem, you want to know the number of paths $a_N$ getting from $0$ to $N$. This number verifies the recursion relation: $$a_N = \sum_{k=1}^6 a_{N-k}$$ provided we set $a_1=1$, $a_k=0$ for $k<0$. We simply partition paths according to the last dice result bringing them to $N$. You may get explicit formulae for this.

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