
Problem 4. Find the number of all natural numbers $n, 4 \leq n \leq$ 1023, such that their binary representations do not contain three consecutive equal digits.

Emil Kolev


Solution: Denote by $a_{n}, n \geq 3$, the number of sequences of zeroes and ones of length $n$ which begin with 1 and do not contain three consecutive equal digits. Also, for any $a, b \in\{0,1\}$ denote by $x_{a b}^{n}$ the number of sequences of zeroes and ones of length $n$ which begin with 1 and do not contain three consecutive equal digits, such that the last two terms are respectively $a$ and $b$. It is easy to see that for $n \geq 5$

$$
x_{00}^{n}=x_{10}^{n-1} ; x_{01}^{n}=x_{00}^{n-1}+x_{10}^{n-1} ; x_{10}^{n}=x_{11}^{n-1}+x_{01}^{n-1} ; x_{11}^{n}=x_{01}^{n-1} .
$$

Adding up the above equalities, we obtain $a_{n}=a_{n-1}+x_{10}^{n-1}+x_{01}^{n-1}=$ $a_{n-1}+a_{n-2}$. Since $a_{3}=3$ and $a_{4}=5$, it follows that $a_{5}=8, a_{6}=13$, $a_{7}=21, a_{8}=34, a_{9}=55$ and $a_{10}=89$.

Since the required number is equal to $a_{3}+a_{4}+\ldots+a_{10}$, it follows from the above that the answer is 228 .
