MathDB
Clever Recursion

Source: 2019 AMC 10B #25/2019 AMC 12B #23

February 14, 2019
AMCAMC 10AMC 10 BAMC 12AMC 12 Bcool solution rusczyk

Problem Statement

How many sequences of 00s and 11s of length 1919 are there that begin with a 00, end with a 00, contain no two consecutive 00s, and contain no three consecutive 11s?
<spanclass=latexbold>(A)</span>55<spanclass=latexbold>(B)</span>60<spanclass=latexbold>(C)</span>65<spanclass=latexbold>(D)</span>70<spanclass=latexbold>(E)</span>75<span class='latex-bold'>(A) </span>55\qquad<span class='latex-bold'>(B) </span>60\qquad<span class='latex-bold'>(C) </span>65\qquad<span class='latex-bold'>(D) </span>70\qquad<span class='latex-bold'>(E) </span>75