6
$\begingroup$

Using the digits $0$, $1$, $2$, $3$, and $4$, how many ten-digit sequences can be written so that the difference between any two consecutive digits is $1$?

I was wondering if my solution is right.

Let $a(n)$ be the number of $n$ digit sequences that end with $0$ or $4$ so that the difference between any two consecutive digits is $1$.

$b(n)$ be the number of n digit sequences that end with $1$ or $3$ so that the difference between any two consecutive digits is $1$.

$c(n)$ be the number of n digit sequences that end with $2$ so that the difference between any two consecutive digits is $1$.

$x(n)$ be the number of n digit sequences so that the difference between any two consecutive digits is $1$.

$x(n) = a(n) + b(n) + c(n)$

$a(n) = b(n-1)$

$b(n) = a(n-1) + 2c(n-1)$

$c(n) = b(n-1)$

By substituting $a(n-1)$ and $c(n-1)$ in the formula for $b(n)$ we get $b(n) = 3b(n-2)$

We know that $b(1) = 2, b(2) = 4$.

The characteristic equation for this recursion is $x^2-3 = 0$ with have the roots $3^{1/2}$ and $-3^{1/2}$, so $b(n) = A{(3^{1/2})}^{n} + B{(-3^{1/2})}^{n}$ where $A = {(3^{1/2}+2)}/{3}$ and $B = {(2-3^{1/2})}/{3}$. I think this is an integer.

We get $x(n) = 2b(n-1) + 3b(n-2)$ and by substituting we get something.

$\endgroup$
3
  • $\begingroup$ You get $b(n)=3b(n-2)$ $\endgroup$ Dec 18 '18 at 7:26
  • $\begingroup$ thanks, i edited it $\endgroup$
    – LIR
    Dec 18 '18 at 8:06
  • $\begingroup$ Looks correct to me $\endgroup$ Dec 18 '18 at 8:14
1
$\begingroup$

Your approach looks good to me but you have to check the final result somehow. You can do that with 15 lines of code:

#include <iostream>
using namespace std;

int count(int startDigit, int length) {
    if(startDigit < 0 || startDigit > 4) {
        return 0;
    }
    if(length == 1)
        return 1;
    return count(startDigit - 1, length - 1) + count(startDigit + 1, length - 1);
}

int main() {
    cout << count(1, 10) + count(2, 10) + count(3, 10) + count(4, 10);
}

...and the result is 567.

$\endgroup$
2
  • 1
    $\begingroup$ I think we should also account for count(0, 10) since it is a sequence and not a number, adding that gives us a result of 648. $\endgroup$ Jun 22 '21 at 18:44
  • $\begingroup$ Nice touch, thanks! $\endgroup$
    – Oldboy
    Jun 25 '21 at 13:08
1
$\begingroup$

here is your answer. Your approach was absolutely correct.

$\endgroup$
1
  • $\begingroup$ $2^3 3^9$ would be the number of 20 digit sequences so that the difference between any two consecutive digits is $1$ i.e. $x(20)$ and not $x(10)$. $\endgroup$ Jun 22 '21 at 18:23
0
$\begingroup$

Your approach is correct, with the above 2 relations mentioned by you: $$a(n) = b(n-1) = c(n)$$ $$b(n) = a(n-1) + 2c(n-1)$$ we can easily get the relation $$x(n)=3x(n-2)$$ Hence $x(10) = 3x(8) = 3^2 x(6) =...= 3^4 x(2)$, where $x(2) = 8$. So, the answer to your question would be $2^3 3^4 = \boldsymbol{648}$

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