1
$\begingroup$

Mark has $N$ days. Initially he is at position $(h1,0)$ on the X-axis. On each day he can go to the co-ordinates $(x+a,0)$ or $(x+b,0)$ or $(x+c,0) .$ where $(x,0)$ is his current position.

He can select any one of the choice he wants. Each day he can go to (+a , +b or +c) from his current position. At the N-th day, he has to reach the position $(h2,0)$. Count the number of ways in which Mark can reach $(h2,0)$ in N days.

Values of $N,h1,h2,a,b,c$ are large(co-ordinates and values of a,b,c can be negative as well, in some cases a=b or b=c or c=a or a=b=c)

My approach is:- At each day, I store the positions which he can reach on that particular day with the count(number of ways) to reach that position. I am using a map to do this. And this approach is not efficient.

Can somebody share a much more efficient approach ?

Can we derive some formula for this problem or a recurrence relation which can solve it efficiently ?

Example:-

N=3,h1=0,h2=6,a=1,b=2,c=3

Answer : -7(number of ways)

1st way:-(1+2+3)

2nd way:-(1+3+2)

3rd way:-(2+1+3)

4th way:-(2+3+1)

5th way:-(3+1+2)

6th way:-(3+2+1)

7th way:-(3+3+1)

Format:-(Choice on 1st day+Choice on 2nd day+Choice on 3rd day)

Also, $1<=N<=10^5$

$\endgroup$
  • 1
    $\begingroup$ Something deep inside me wants to scream "knapsack problem" (en.wikipedia.org/wiki/Knapsack_problem) So the only thing I can say is that the number you are looking for is going to be exponential in the number of days. Also, could you show the 7 possibilities you have found for your example? $\endgroup$ – Milloupe Jun 26 at 8:42
  • 1
    $\begingroup$ Oh, except that your constraints are much stricter than the knapsack problem (because you have an exact number of days to reach the destination, which the knapsack problem does not have), so sometimes you just won't have any solutions either. This means that there won't be any "simple" recurrence formula. $\endgroup$ – Milloupe Jun 26 at 8:46
  • 1
    $\begingroup$ @Milloupe To me, it seemed like coin-exchange problem such that you also have to keep checking the number of coins(N). I've showed the 7-ways in my answer now $\endgroup$ – Firex Firexo Jun 26 at 8:51
  • 2
    $\begingroup$ Oh you're right, it is much closer to the coin-exchange problem, my bad. Except, again, the fixed number of days, which causes some cases to have no answers $\endgroup$ – Milloupe Jun 26 at 8:55
  • $\begingroup$ Well for starters, every integer $h2-h1$ that is not a multiple of $\gcd({a,b,c})$ cannot be expressed as their linear combination, let alone a combination that equals $h2-h1$ in $N$ days. If $a=b=c$ then it is trivial. The $a=b\lt c$ case could be simpler to look at first, then WLOG $a\lt b \lt c$. But as already discussed in comments, this is the coin change problem with an additional restriction of using exactly $N$ coins total (Except also that you are allowing negative coins). $\endgroup$ – Vepir Jun 26 at 10:05
2
$\begingroup$

This is an algebraic approach to count the number of ways. We start with OP's example.

We consider $N=3,h_1=0,h_2=6,a=1,b=2$ and $c=3$.

  • Each day we can walk either $1,2$ or $3$ steps. We encode this as $x^{\color{blue}{1}}+x^{\color{blue}{2}}+x^{\color{blue}{3}}$

  • We do these walks in $N=3$ days and encode this as $(x^1+x^2+x^3)^{\color{blue}{3}}$.

  • Since we are interested in the number of ways to go length $h_2=6$ we are looking for $[x^{\color{blue}{6}}] (x^1+x^2+x^3)^3$ where $[x^k]$ denotes the coefficient of $x^k$.

We obtain \begin{align*} \color{blue}{[x^6]\left(x+x^2+x^3\right)^3}&=[x^6]x^3\left(1+x+x^2\right)^3\\ &=[x^3]\sum_{j=0}^3\binom{3}{j}\left(x+x^2\right)^j\tag{1}\\ &=[x^3]\sum_{j=0}^3\binom{3}{j}x^j\left(1+x\right)^j\\ &=\sum_{j=0}^3\binom{3}{j}[x^{3-j}](1+x)^j\tag{2}\\ &=\sum_{j=0}^3\binom{3}{j}[x^{3-j}]\sum_{k=0}^j\binom{j}{k}x^k\\ &=\sum_{j=0}^3\binom{3}{j}\binom{j}{3-j}\tag{3}\\ &=\binom{3}{2}\binom{2}{1}+\binom{3}{3}\binom{3}{0}\tag{4}\\ &=3\cdot 2+1\cdot 1\\ &\,\,\color{blue}{=7} \end{align*}

Comment:

  • In (1) we use the binomial theorem and apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.

  • In (2) we again the rule as we did in (1).

  • In (3) we select the coefficient of $x^{3-j}$.

  • In (4) we note that only summands with $j\geq 2$ give a contribution since $\binom{p}{q}=0$ if $q>p\geq 0$.

The general case is similarly to the example above. As it is somewhat more technical it might be slightly more cumbersome.

We consider WLOG $h_1=0$, since the number of ways from $h_1$ to $h_2$ is the same as from $0$ to $h_2-h_1$. Here we consider only $0<a<b<c$. Other cases can be derived similarly.

We obtain \begin{align*} \color{blue}{[x^{h_2}]}&\color{blue}{\left(x^a+x^b+x^c\right)^{N}}\\ &=[x^{h_2}]x^{aN}\left(1+x^{b-a}+x^{c-a}\right)^{N}\\ &=[x^{h_2-aN}]\sum_{j=0}^{N}\binom{N}{j}\left(x^{b-a}+x^{c-a}\right)^j[[h_2\geq aN]]\tag{5}\\ &=[x^{h_2-aN}]\sum_{j=0}^{N}\binom{N}{j}x^{(b-a)j}\left(1+x^{c-b}\right)^j[[h_2\geq aN]]\\ &=\sum_{j=0}^{\min\left\{N,\left\lfloor\frac{h_2-aN}{b-a}\right\rfloor\right\}}\binom{h_2}{j}[x^{h_2-aN-(b-a)j}] \sum_{k=0}^j\binom{j}{k}x^{(c-b)k}[[h_2\geq aN]]\tag{6}\\ &\,\,\color{blue}{=\sum_{{j=0}\atop{h_2-aN-(b-a)j\mid c-b}}^{\min\left\{N,\left\lfloor\frac{h_2-aN}{b-a}\right\rfloor\right\}}\binom{N}{j} \binom{j}{\frac{h_2-aN-(b-a)j}{c-b}}[[h_2\geq aN]]}\tag{7}\\ \end{align*}

Comment:

  • In (5) we work analogously to (1) and we use Iverson brackets since for non-zero summands we have to assure that $h_2\geq aN$.

  • In (6) we work analgously to (2). We also set the upper limit of the sum to a minimum to assure that $h_2-aN-(b-a)j\geq 0$.

  • In (7) we select the coefficient of $x^{h_2-aN-(b-a)j}$ by respecting that the exponent is a multiple of $c-b$.

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