2014 AIME II Problem 9

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

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

9.

Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least three adjacent chairs.

Answer: 581
Concepts:circular arrangementssubsetsinclusion-exclusion
Difficulty rating: 2760
Solution:

The full set of 1010 chairs qualifies; count the others by locating each maximal run of at least three adjacent chosen chairs at its clockwise start. Any such subset contains a block of four consecutive chairs that is empty-chosen-chosen-chosen. There are 1010 positions for this block, and the remaining 66 chairs are free, giving 1026=640.10 \cdot 2^6 = 640.

This counts once for each maximal run of length at least 3.3. Two such runs require at least 3+33 + 3 chosen chairs plus two gaps, so three runs are impossible, and subsets with exactly two runs are counted twice. To have two runs, place two disjoint empty-chosen-chosen-chosen blocks: 1032=15\frac{10 \cdot 3}{2} = 15 ways (the second block fits in 33 positions among the remaining 66 chairs), with the last 22 chairs free, for 1522=6015 \cdot 2^2 = 60 subsets.

The total is 1+64060=581.1 + 640 - 60 = 581.

← Problem 8#8
Full Exam

Problem 9 in Other Years