2020 AIME II Problem 9

Attempt Problem 9 of the 2020 AIME II 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 2020 AIME II solutions, or check the answer key.

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

9.

While watching a show, Ayako, Billy, Carlos, Dahlia, Ehuang, and Frank sat in that order in a row of six chairs. During the break, they went to the kitchen for a snack. When they came back, they sat on those six chairs in such a way that if two of them sat next to each other before the break, then they did not sit next to each other after the break. Find the number of possible seating orders they could have chosen after the break.

Answer: 90
Concepts:arrangements with restrictionsinclusion-exclusionpermutations
Difficulty rating: 2840
Solution:

Number the friends 11 through 66 in original seating order; we count orderings of 1,,61, \ldots, 6 in which no two consecutive integers are adjacent. Apply inclusion-exclusion over which of the five pairs {i,i+1}\{i, i+1\} are forced to sit together. If a chosen set of kk pairs forms rr maximal runs of consecutive integers, gluing each run into a block (orderable ascending or descending) gives 2r(6k)!2^r (6 - k)! seatings containing all chosen adjacencies.

Tallying by k:k: for k=0,k = 0, 720.720. For k=1,k = 1, five sets, each 2120,2 \cdot 120, total 1200.1200. For k=2,k = 2, four sets form one run (224)(2 \cdot 24) and six form two runs (424),(4 \cdot 24), total 768.768. For k=3,k = 3, three sets form one run (26),(2 \cdot 6), six form two runs (46),(4 \cdot 6), one forms three runs (86),(8 \cdot 6), total 228.228. For k=4,k = 4, two sets form one run (22)(2 \cdot 2) and three form two runs (42),(4 \cdot 2), total 32.32. For k=5,k = 5, one set, total 2.2.

The count is 7201200+768720 - 1200 + 768 228+322=90.- 228 + 32 - 2 = 90.

← Problem 8#8
Full Exam

Problem 9 in Other Years