IMO 1987 SL 14

Origin: FRG

Problem

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?

Solution

Let xn be the total number of counted words of length n, and yn, zn, un, zn, yn the numbers of counted words of length n starting with 0, 1, 2, 3, 4, respectively (indeed, by symmetry, words starting with 0 are equally num- bered as those starting with 4, etc.). We have the clear relations (1) yn = zn−1; (2) zn = yn−1 + un−1; (3) un = 2zn−1; (4) xn = 2yn + 2zn + un. From (1), (2), and (3) we get zn = zn−2 + 2zn−2 = 3zn−2, with z1 = 1, z2 = 2, which gives z2n = 2 \cdot 3n−1, z2n+1 = 3n. Then (1), (3), and (4) obviously imply y2n = 3n−1, y2n+1 = 2 \cdot 3n−1; u2n = 2 \cdot 3n−1, u2n+1 = 4 \cdot 3n−1; x2n = 8 \cdot 3n−1, x2n+1 = 14 \cdot 3n−1; with the initial number x1 = 5.