2014 AIME II Problem 9

Below is the professionally curated solution for Problem 9 of the 2014 AIME II, 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 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:circular arrangementssubsetsinclusion-exclusion

Difficulty rating: 2760

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.

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 8Full ExamProblem 10

Problem 9 in Other Years