Maths Olympiad Prep

Library / /159 of 348

Combinatorics Difficulty 4.9 AIME Find the answer

How many sequences of ten binary digits are there in which neither two zeroes nor three ones ever appear in a row?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let ana_{n} be the number of binary sequences of length nn satisfying the conditions and ending in 0 , let bnb_{n} be the number ending in 01 , and let cnc_{n} be the number ending in 11 . From the legal sequences of length 201,11,10201,11,10, we find that a2=b2=c2=1a_{2}=b_{2}=c_{2}=1. We now establish a recursion by building sequences of length n+1n+1 from sequences of length nn. We can add a 0 to a sequence of length nn if and only if it ended with a 1 , so an+1=bn+cna_{n+1}=b_{n}+c_{n}. We can have a sequence of length n+1n+1 ending with 01 only by adding a 1 to a sequence of length nn ending in 0 , so bn+1=anb_{n+1}=a_{n}. We can have a sequence of length n+1n+1 ending with 11 only by adding a 1 to a sequence of length nn ending in 01 , so cn+1=bnc_{n+1}=b_{n}. We can now run the recursion: \begin{tabular}{c|c|c|c} nn & ana_{n} & bnb_{n} & cnc_{n} \\ \hline 2 & 1 & 1 & 1 \\ \hline 3 & 2 & 1 & 1 \\ \hline 4 & 2 & 2 & 1 \\ \hline 5 & 3 & 2 & 2 \\ \hline 6 & 4 & 3 & 2 \\ \hline 7 & 5 & 4 & 3 \\ \hline 8 & 7 & 5 & 4 \\ \hline 9 & 9 & 7 & 5 \\ \hline 10 & 12 & 9 & 7 \end{tabular} Our answer is then 12+9+7=2812+9+7=28.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.