1
$\begingroup$

We call a number to be good if none of two consecutive digits differ by more than one. How many good $n$-digits numbers made from digits $1$, $2$ and $3$ are there?

For example, $12232$ is good, but $12\textbf{31}2$ isn't.

My idea was to subtract bad numbers made of $1$, $2$ and $3$ (bad numbers are ones that aren't good) from $3^n$ (which represents number of $n$-digit numbers made of $1$, $2$ and $3$).

I tried with representing number $abcd$ ($n=4$) as sequence of 3 ($4-1$) pairs of digits: $(a,b),\text{ }(b,c),\text{ }(c,d)$. Then (I think) we could count number of ways to have at least one of the pairs $(1,3)$ and $(3,1) appearing at least once. But alas...

$\endgroup$
3
$\begingroup$

Let $A_n, B_n, C_n$ be the number of ways an $n-$digit number satisfies the condition, and starts with $1, 2, 3$ respectively. We have $A_1 = B_1 = C_1 = 1$. We are looking for $A_n + B_n + C_n$.

The recurrence relation is $A_{n+1} = A_n + B_n$, $B_{n+1} = A_n + B_n + C_n$, $C_{n+1} = B_n + C_n$. By symmetry, we have $C_n = A_n$.

Claim: $A_n \sqrt{2} +B_n= (\sqrt{2}+1 )^{n+1}$.

Proof: This is true for $n=1$. Proceed by induction to show that the recurrence relation is satisfied. $_\square$

Similarly, $A_n \sqrt{2} - B_n = (\sqrt{2} -1)^{n+1}$. This allows you to obtain closed forms for $A_n$ and $B_n$.

$\endgroup$
1
$\begingroup$

Let the $n$ digit number be $a_1 a_2 \ldots a_n$. Let $N_1(n)$ be the number of $n$ digit numbers that are good starting with $1$, $N_2(n)$ be the number of $n$ digit numbers that are good starting with $2$ and , $N_3(n)$ be the number of $n$ digit numbers that are good starting with $3$. We have \begin{align} N_1(n) & = N_1(n-1) + N_2(n-1)\\ N_2(n) & = N_1(n-1) + N_2(n-1) + N_3(n-1)\\ N_3(n) & = N_2(n-1) + N_3(n-1) \end{align} Hence, we have $$\begin{bmatrix}N_1(n)\\ N_2(n)\\ N_3(n) \end{bmatrix} = \underbrace{\begin{bmatrix} 1 & 1 & 0\\ 1 & 1 & 1\\ 0 & 1 &1\end{bmatrix}}_A \begin{bmatrix} N_1(n-1)\\ N_2(n-1)\\ N_3(n-1) \end{bmatrix}$$ Hence, $$\vec{N}(n+1) = A^n \vec{N}(1)$$ We have $$V = \dfrac12 \begin{bmatrix} 1 & -\sqrt2 & 1\\ -\sqrt2 & 0 & \sqrt 2\\ 1 & \sqrt2 & 1\end{bmatrix}$$ and $$\Lambda = \begin{bmatrix} 1-\sqrt2 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & 1 +\sqrt2\end{bmatrix}$$ and $$A = V \Lambda V^T$$ Hence, $$\vec{N}(n+1) = V \Lambda^n V^T \vec{N}(1)$$ where $$\vec{N}(1) = \begin{bmatrix} 1 \\ 1 \\ 1\end{bmatrix}$$ Hence, the answer is \begin{align} N_1(n) + N_2(n) + N_3(n) & = \begin{bmatrix} 1 & 1 & 1\end{bmatrix} V \Lambda^n V^T \begin{bmatrix} 1 \\ 1 \\ 1\end{bmatrix}\\ & = \dfrac14\begin{bmatrix} 2-\sqrt{2} & 0 & 2+\sqrt{2}\end{bmatrix} \begin{bmatrix} (1-\sqrt2)^{n-1} & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & (1 +\sqrt2)^{n-1}\end{bmatrix}\begin{bmatrix} 2-\sqrt{2} \\ 0 \\ 2+\sqrt{2}\end{bmatrix}\\ & = \dfrac12\begin{bmatrix} \sqrt{2}-1 & 0 & 1+\sqrt{2}\end{bmatrix} \begin{bmatrix} (1-\sqrt2)^{n-1} & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & (1 +\sqrt2)^{n-1}\end{bmatrix}\begin{bmatrix} \sqrt{2}-1 \\ 0 \\ 1+\sqrt{2}\end{bmatrix}\\ & = \dfrac{(1+\sqrt2)^{n+1} + (1-\sqrt2)^{n+1}}2 \end{align}

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