How many words with $n$ digits can be formed from the alphabet $\{0, 1, 2, 3, 4\}$, if neighboring digits must differ by exactly one? Proposed by Germany, FR.
Problem
Source:
Tags: symmetry, combinatorics, Combinatorics of words, counting, Digits, recurrence relation, IMO Shortlist
uglysolutions
20.08.2010 03:53
Let $a_n,b_n,c_n$ be the number of words with $n$ digits ending in $0,1,2$ respectively. By symmetry, $a_n,b_n$ are also the number of words with $n$ digits ending in $4,3$ respectively. We want to compute $S_n = 2a_n + 2b_n + c_n$. We have $a_1 = b_1 = c_1 = 1$, and the following relations hold: $a_{n+1} = b_n$ $b_{n+1} = a_n + c_n$ $c_{n+1} = 2b_n$ (These arise from facts like: we can add a $0$ at the end of a word iff its last digit is $1$, etc) We'll prove by induction that $b_{2n+1} = 3^n$. This is true for $n=0$. Suppose it's true for $n-1$, then $b_{2n-1} = 3^{n-1} \Rightarrow a_{2n} = 3^{n-1}, c_{2n} = 2\cdot3^{n-1} \Rightarrow b_{2n+1} = 3^n$ as wanted. Thus, $a_{2n+2} = 3^n$ and $c_{2n+2} = 2\cdot3^n$. Now, again by induction, let's see that $b_{2n+2} = 2\cdot3^n$. This is true for $n=0$. Suppose it's true for $n-1$, then $b_{2n} = 2\cdot3^{n-1} \Rightarrow a_{2n+1} = 2\cdot3^{n-1}, c_{2n+1} = 4\cdot3^{n-1} \Rightarrow b_{2n+2} = 2\cdot3^n$. Hence $a_{2n+3} = 2\cdot3^n$ and $c_{2n+3} = 4\cdot3^n$. From what we've done so far we get $S_1 = 5$ $S_{2n+2} = 2\cdot3^n + 4\cdot3^n + 2\cdot3^n = 8\cdot3^n$ for all $n\geq0$ $S_{2n+3} = 4\cdot3^n + 2\cdot3^{n+1} + 4\cdot3^n = 14\cdot3^n$ for all $n\geq0$.
AK1024
21.08.2010 22:27
Here was my solution from a while ago: I will define a powerful word to be a word that can be formed using the characters $0,1,2,3,4$ and consecutive digits differing by $1$. Let $W(n)$ be the number of good words with $n$ digits. By inspection, $W(1)=5, W(2)=8, W(3)=14, W(4)=24$. Let $W_a(n)$ be similarly defined as $W(n)$ but with the condition that the word starts with the character $a$. By symmetry, $W_0(n)=W_4(n)$ and $W_1(n)=W_3(n)$ for all natural $n$. Thus $W(n)=2W_0(n)+2W_1(n)+W_2(n)$. It is clear that if $\overline{d_1d_2d_3\ldots d_n}$ is powerful, then so is $\overline{d_1d_2\ldots d_{n-1}}$. $W_0(2m+1)=2W_0(2m)$
Since $W_0(x)$ begins with $0$ for all $x$, every second digit is odd. Let $\overline{d_1d_2\ldots d_{2m+1}}$ be a powerful word, and hence so is $\overline{d_1d_2\ldots d_{2m}}$. Note $d_{2m}\in \{1,3 \}$, and $d_{2m}=1 \implies d_{2m+1}$ equals $0$ or $2$ and $d_{2m}=1 \implies d_{2m+1}$ equals $2$ or $4$. Equivalently, every powerful word of length $2m$ generates $2$ powerful words of length $2m+1$, and no other powerful words with $2m+1$ digits exist (otherwise the first $2m$ digits would be powerful). Thus $W_0(2m+1)=2W_0(2m)$.
$W_0(2m+2)=3W_0(2m)$
We know that when ${\overline{d_1d_2\ldots d_{2m}d_{2m+1}d_{2m+2}}}$ is powerful so is $\overline{d_1d_2\ldots d_{2m}}$. The last digit of the latter is odd, and we will assume it equals $1$. Then the only possibilities of $\overline{d_{2m+1}d_{2m+2}}$ are $01,21,23$. These are replaced by symmetric suffixes when the last digit is $3$. So each $2m$ digit powerful word generates $3$ powerful words with $2m+2$ digits. As it is easy to verify no other $2m+3$ digits can be formed, we conclude $W_0(2m+2)=3W_0(2m)$.
From the second result, after verifying $W_0(2)=1$, we can apply induction to show that $W_0(2m)=3^{m-1}$. Then by the first relation, we have, in summary: \[W_0(a)= \begin{cases} 3^{\displaystyle\frac{a}{2}-1} & \mbox{if }a\mbox{ is even} \\ 2\cdot3^{\displaystyle\frac{a-1}{2}-1} & \mbox{if }a\mbox{ is odd}, a>3 \\ 1 & a=1\\ 2 & a=3 \end{cases}\] Now for $W_1(a)$. This is simpler. Imagine all of the powerful words beginning with $0$, and hence the second digit $1$, but with the $0$ digit invisible. Then we have a $a-1$ digit powerful word beginning with $1$. Hence $W_1(a)=W_0(a)+1$. Therefore \[W_1(a)= \begin{cases} 2\cdot 3^{\displaystyle\frac{a}{2}-1} & \mbox{if }a\mbox{ is even}, a>2 \\ 3^{\displaystyle\frac{a-1}{2}} & \mbox{if }a\mbox{ is odd} \\ 2 & a=2 \end{cases}\] $W_2(a)$ is again simple. Imagine the $2$ at the start invisible. Then we have powerful words of length $a-1$ beginning with $1$ and $3$. Thus $W_2(a)=W_1(a-1)+W_3(a-1)=2W_1(a-1)$. Thus: \[W_2(a)= \begin{cases} 2\cdot 3^{\displaystyle\frac{a}{2}-1} & \mbox{if }a\mbox{ is even} \\ 2\cdot 3^{\displaystyle\frac{a-1}{2}-1} & \mbox{if }a\mbox{ is odd}, a>1 \\ 1 & a=1 \end{cases}\] Therefore $W(1)=5, W(2)=8, W(3)=14$ and for $2n,2n+1\ge 4$ we have \[W(2n)=2(3^{n-1})+2(2\cdot 3^{n-1})+2\cdot 3^{n-1}=8\cdot 3^{n-1} \] \[W(2n+1)= 2(2\cdot 3^{n-1})+2(3^n)+2\cdot 3^{n-1}=14\cdot 3^{n-1}\] EDIT: fixed a typo