How many words with $N$-characters can be formed from the numbers $\{0, 1, 2\}$, such that adjacent numbers have maximum difference $1$? Example: For $N = 2$ there are $7$ words that can be formed: $<0,0>;<0,1>;<1,0>; <1,1>; <1,2>; <2,1>; <2,2>$. The $<>$ notation specifies a single word. If $N = 10$, how many words can be formed?
a. 8119
b. 8121
c. 8123
d. 8125
e. 8127

I have tried to answer this problem by counting all possible words, then subtracting those words that violate the rules, but I found the answer isn't one of the choices.

$<a, b, c, d, e, f, g, h, i, j>$

All combination is $3^{10} = 59049$
when the difference is more than $1$ then the only possibility is that the word contains a $0$ and a $2$ that are adjacent to each other.

Please help me THANK YOU!


marked as duplicate by Shailesh, hardmath, Aqua, GNUSupporter 8964民主女神 地下教會, Leucippus Dec 20 '17 at 0:06

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Oh I knew! this is a dynamic programming question, isn't it? $\endgroup$ – Dimas Riatmodjo Dec 19 '17 at 9:23
  • $\begingroup$ @the4seasons The linked question is similar but not a duplicate! $\endgroup$ – Robert Z Dec 19 '17 at 9:23
  • $\begingroup$ Ahh I saw that the solutions were similar... sorry, and thanks. $\endgroup$ – the4seasons Dec 19 '17 at 9:49

Hint. Let $a_N$, $b_N$ and $c_N$ be the number of $N$-character strings that can be formed from $\{0,1,2\}$, such that adjacent numbers have the maximum difference $1$ and it ends with $0$, $1$, and $2$ respectively. Moreover let $s_N=a_N+b_N+c_N$ be the total number of such $N$-character strings. Then, for $N\geq 1$, they satisfy the recurrences $$\begin{cases} a_{N+1}=a_N+b_N &\text{(before the ending $0$ there is $0$ or $1$)}\\ b_{N+1}=a_N+b_N+c_N=s_N &\text{(before the ending $1$ there is $0$, $1$ or $2$)}\\ c_{N+1}=b_N+c_N &\text{(before the ending $2$ there is $1$ or $2$)} \end{cases}$$ Hence, by taking the sum of these three recurrences, we find $$s_{N+1}=2s_N+b_N=2s_N+s_{N-1}.$$ Now $s_1=3$ and $s_2=7$ (see your remark). Can you take it from here and find $s_{10}$?

  • $\begingroup$ Thank you so much!! I love this solution. Actually I have found the right solution by myself, but this solution is much simpler and much clearer than mine :D $\endgroup$ – Dimas Riatmodjo Dec 19 '17 at 9:27
  • $\begingroup$ I still confused. Why b[N] is equal to s[N-1]? $\endgroup$ – Dimas Riatmodjo Dec 19 '17 at 9:33
  • 1
    $\begingroup$ Because $b_{N+1}=a_N+b_N+c_N$ and $s_N=a_N+b_N+c_N$. $\endgroup$ – Robert Z Dec 19 '17 at 9:44
  • $\begingroup$ Ok I understand now. Thanks $\endgroup$ – Dimas Riatmodjo Dec 19 '17 at 9:46

Not the answer you're looking for? Browse other questions tagged or ask your own question.