2023 AIME I Problem 11

Below is the professionally curated solution for Problem 11 of the 2023 AIME I, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:subsetsFibonaccicasework

Difficulty rating: 2650

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\}.

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.\sum_{k=1}^{9} F_k F_{10-k} = 34 + 21 + 26 + 24 + 25 + 24 + 26 + 21 + 34 = 235.

← Problem 10Full ExamProblem 12

Problem 11 in Other Years