2008 AIME I Problem 11

Attempt Problem 11 of the 2008 AIME I below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2008 AIME I solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

11.

Consider sequences that consist entirely of AA's and BB's and that have the property that every run of consecutive AA's has even length, and every run of consecutive BB's has odd length. Examples of such sequences are AA,AA, B,B, and AABAA,AABAA, while BBABBBAB is not such a sequence. How many such sequences have length 14?14?

Answer: 172
Concepts:recursive countingarrangements with restrictionsparity
Difficulty rating: 2920
Solution:

Let ana_n and bnb_n count valid sequences of length nn beginning with AA and with B.B. A sequence beginning with AA starts with AAAA followed by any valid sequence of length n2n - 2 (possibly empty), so an+2=an+bn,a_{n+2} = a_n + b_n, where the empty sequence counts once. A sequence beginning with BB starts either with a single BB followed by a sequence beginning with A,A, or with BBBB followed by a sequence beginning with B,B, so bn+2=an+1+bn.b_{n+2} = a_{n+1} + b_n.

Starting from (a1,b1)=(0,1)(a_1, b_1) = (0, 1) and (a2,b2)=(1,0),(a_2, b_2) = (1, 0), the pairs (an,bn)(a_n, b_n) for n=3,4,,14n = 3, 4, \ldots, 14 are (1,2), (1,1), (3,3), (2,4), (6,5), (6,10), (11,11), (16,21), (22,27), (37,43), (49,64), (80,92). \begin{aligned} &(1, 2),\ (1, 1),\ (3, 3),\ \\ &(2, 4),\ (6, 5),\ (6, 10),\ \\ &(11, 11),\ (16, 21),\ (22, 27),\ \\ &(37, 43),\ (49, 64),\ (80, 92). \end{aligned}

The number of valid sequences of length 1414 is 80+92=172.80 + 92 = 172.

← Problem 10#10
Full Exam

Problem 11 in Other Years