During AMC testing, the AoPS Wiki is in read-only mode. No edits can be made.

# Difference between revisions of "2014 AIME II Problems/Problem 9"

## Problem

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 1 (Casework)

We know that a subset with less than $3$ chairs cannot contain $3$ adjacent chairs. There are only $10$ sets of $3$ chairs so that they are all $3$ adjacent. There are $10$ subsets of $4$ chairs where all $4$ are adjacent, and $10 * 5$ or $50$ where there are only $3.$ If there are $5$ chairs, $10$ have all $5$ adjacent, $10 * 4$ or $40$ have $4$ adjacent, and $10 * {5\choose 2}$ or $100$ have $3$ adjacent. With $6$ chairs in the subset, $10$ have all $6$ adjacent, $10(3)$ or $30$ have $5$ adjacent, $10 * {4\choose2}$ or $60$ have $4$ adjacent, $\frac{10 * 3}{2}$ or $15$ have $2$ groups of $3$ adjacent chairs, and $10 * ({5\choose2} - 3)$ or $70$ have $1$ group of $3$ adjacent chairs. All possible subsets with more than $6$ chairs have at least $1$ group of $3$ adjacent chairs, so we add ${10\choose7}$ or $120$, ${10\choose8}$ or $45$, ${10\choose9}$ or $10$, and ${10\choose10}$ or $1.$ Adding, we get $10 + 10 + 50 + 10 + 40 + 100 + 10 + 30 + 60 + 15 + 70 + 120 + 45 + 10 + 1 = \boxed{581}.$

## Solution 2 (PIE)

Starting with small cases, we see that four chairs give 4 + 1 = 5, five chairs give 5 + 5 + 1 = 11, and six chairs give 6 + 6 + 6 + 6 + 1 = 25. Thus, I claim that n chairs give $n 2^{n-4} + 1$, as confirmed above. This claim can be verified by PIE: there are $n 2^{n-3}$ ways to arrange 3 adjacent chairs, but then we subtract $n 2^{n-4}$ ways to arrange 4. Finally, we add 1 to account for the full subset of chairs. Thus, for n = 10 we get a first count of 641.

However, we overcount cases in which there are two distinct groups of three or more chairs. Time to casework: we have 5 cases for two groups of 3 directly opposite each other, 5 for two groups of four, 20 for two groups of 3 not symmetrically opposite, 20 for a group of 3 and a group of 4, and 10 for a group of 3 and a group of 5. Thus, we have 641 - 60 = $\boxed{581}$.

## Solution 3 (Complementary Counting)

It is possible to use recursion to count the complement. Number the chairs 1, 2, 3, ..., 10. If chair 1 is not occupied, then we have a line of 9 chairs such that there is no consecutive group of three. If chair 1 is occupied, then we split into more cases. If chairs 2 and 10 are empty, then we have a line of 7. If chair 2 is empty but chair 10 is occupied, then we have a line of 6 chairs (because chair 9 cannot be occupied); similarly for chair 2 occupied and chair 10 empty. Finally, chairs 2 and 10 cannot be simultaneously occupied. Thus, we have reduced the problem down to computing $T_9 + T_7 + 2T_6$, where $T_n$ counts the ways to select a subset of chairs from a group of n chairs such that there is no group of 3 chairs in a row.

Now, we notice that $T_n = T_{n-1} + T_{n-2} + T_{n-3}$ (representing the cases when the first, second, and/or third chair is occupied). Also, $T_0 = 1, T_1 = 2, T_2 = 4, T_3 = 7$, and hence $T_4 = 13, T_5 = 24, T_6 = 44, T_7 = 81, T_8 = 149, T_9 = 274$. Now we know the complement is $274 + 81 + 88 = 443$, and subtracting from $2^{10} = 1024$ gives $1024 - 443 = \boxed{581}$.