2023 AIME I Problem 11

Attempt Problem 11 of the 2023 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 2023 AIME I solutions, or check the answer key.

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

11.

Find the number of subsets of {1,2,3,,10}\{1, 2, 3, \ldots, 10\} that contain exactly one pair of consecutive integers. Examples of such subsets are {1,2,5}\{\mathbf{1}, \mathbf{2}, 5\} and {1,3,6,7,10}.\{1, 3, \mathbf{6}, \mathbf{7}, 10\}.

Answer: 235
Concepts:subsetsFibonaccicasework
Difficulty rating: 2650
Solution:

First, the number of subsets of a block of mm consecutive integers containing no two consecutive elements is the Fibonacci number Fm+2F_{m+2} (with F1=F2=1F_1 = F_2 = 1): conditioning on whether the last element is used gives the Fibonacci recursion, and the counts start 1,2,3,5,1, 2, 3, 5, \ldots

Suppose the unique consecutive pair is {k,k+1}\{k, k+1\} for some 1k9.1 \le k \le 9. The remaining elements must exclude k1k - 1 and k+2k + 2 (either would create a second consecutive pair) and must contain no consecutive pair within {1,,k2}\{1, \ldots, k-2\} or within {k+3,,10},\{k+3, \ldots, 10\}, blocks of sizes k2k - 2 and 8k.8 - k. So the count for this kk is FkF10k.F_k \cdot F_{10-k}.

Summing over k=1,,9:k = 1, \ldots, 9: k=19FkF10k=34+21+26+24+25+24+26+21+34=235. \begin{aligned} \sum_{k=1}^{9} F_k F_{10-k} &= 34 + 21 + 26 \\ &\quad {}+ 24 + 25 + 24 \\ &\quad {}+ 26 + 21 + 34 \\ &= 235. \end{aligned}

← Problem 10#10
Full Exam

Problem 11 in Other Years