Saudi Arabia booklet 2024

Consider 19 consecutive squares and color them yellow (corresponding to houses that receive letters) and white (corresponding to houses that do not receive letters). Then, according to the assumption, there are no 2 consecutive yellow cells and no 3 consecutive white cells. We need to calculate the number of such coloring ways and in general, let $S_n$ be the number of coloring ways in case there are a total of $n$ squares.

Notice that for any two adjacent squares, there are only three cases: $YW$, $WY$, $WW$. Let $a_n$ be the number of coloring ways where the last 2 cells are $YW$, let $b_n$ be the number of coloring ways where the last 2 cells are $WY$ and let $c_n$ be the number of ways to fill the last 2 cells with $WW$. We will establish some recurrence relationships for the sequences as follows:

With $(a_n)$: notice that before $YW$ it must be $YW$ or $WW$ so $a_{n+2}=a_n+c_n$. With $(b_n)$: before $WY$ it must be $YW$ or $WY$ so $b_{n+2}=a_n+b_n$. * With $(c_n)$: before $WW$ it can only be $WY$ so $c_{n+2}=b_n$.

Note that $S_n=a_n+b_n+c_n$ and we also have $$c_n=b_{n-2},a_{n+2}=b_{n-2}+a_n.$$ From these, we get $b_n=a_{n+4}-a_{n+2}$ so replace it back with $b_{n+2}=a_n+b_n$ then $$a_{n+6}=2a_{n+4}-a_{n+2}+a_n.$$ Thus $S_n=a_n+(a_{n+4}-a_{n+2})+(a_{n+2}-a_n)=a_{n+4}$ so we immediately have the formula for $(S_n)$ is $$S_{n+2}=2S_n-S_{n-2}+S_{n-4},\forall n\ge 5.$$ It is easy to check that $S_1=2$, $S_2=3$, $S_3=4$, $S_4=5$ so substituting into above formula to get $S_{19}=351$. This is also the number of ways to deliver the mail that need to find. $\boxed{351}$