5
$\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 recurssion 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$
  • $\begingroup$ You get $b(n)=3b(n-2)$ $\endgroup$ – Shubham Johri Dec 18 '18 at 7:26
  • $\begingroup$ thanks, i edited it $\endgroup$ – Lazar Ionut Radu Dec 18 '18 at 8:06
  • $\begingroup$ Looks correct to me $\endgroup$ – Shubham Johri Dec 18 '18 at 8:14
0
$\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$
0
$\begingroup$

here is your answer. Your approach was absolutely correct.

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