A sequence composed by $0$s and $1$s has at most two consecutive $0$s. How many sequences of length $10$ exist?
Problem
Source: 2024 Portuguese MO Day 1 P3
Tags: combinatorics
01.05.2024 18:14
Let $S(n)$ be the number of such sequences. Let $P(n)$ be the number of such sequences ending in $1$. Firstly, notice that if $P(n)$ ends with $11$, we have $P(n) = P(n - 1)$, if $P(n)$ ends with 101, $P(n) = P(n - 2)$, if $P(n)$ ends with $1001$, $P(n) = P(n - 3)$: $$\implies P(n) = P(n - 1) + P(n - 2) + P(n - 3)$$Since we can have at most two consecutive zeroes, we have $S(n) = P(n) + P(n - 1) + P(n - 2) = 2P(n - 1) + 2P(n - 2) + P(n - 3)$. What we need to do is to find $S(10)$, so we can simply spam the above relation until obtain an easy $n$ (3), which gives an answer of $\boxed{504}$.
10.08.2024 22:40
Let the number of sequences be $a_i$ The last digit of $1$ might appear in place $i$, $i-1$ or $i-2$ in the sequence (no more earlier as there will be three $0$s consecutive at the end) So $a_i=a_{i-1}+a_{i-2}+a_{i-3}$. we have $a_1=2, a_2=4, a_3=7, a_4=13, a_5=24, a_6=44, a_7=81, a_8=149, a_9=274$ so $a_{10}=504$ which is the answer