Difference between revisions of "2014 AIME II Problems/Problem 9"
(→Solution 3 (Complementary Counting)) |
(→Solution 3 (Complementary Counting)) |
||
Line 15: | Line 15: | ||
Now, we notice that <math>T_n = T_{n-1} + T_{n-2} + T_{n-3}</math> (representing the cases when the first, second, and/or third chair is occupied). Also, <math>T_0 = 1, T_1 = 2, T_2 = 4, T_3 = 7</math>, and hence <math>T_4 = 13, T_5 = 24, T_6 = 44, T_7 = 81, T_8 = 149, T_9 = 274</math>. Now we know the complement is <math>274 + 81 + 88 = 443</math>, and subtracting from <math>2^{10} = 1024</math> gives <math>1024 - 443 = \boxed{581}</math>. | Now, we notice that <math>T_n = T_{n-1} + T_{n-2} + T_{n-3}</math> (representing the cases when the first, second, and/or third chair is occupied). Also, <math>T_0 = 1, T_1 = 2, T_2 = 4, T_3 = 7</math>, and hence <math>T_4 = 13, T_5 = 24, T_6 = 44, T_7 = 81, T_8 = 149, T_9 = 274</math>. Now we know the complement is <math>274 + 81 + 88 = 443</math>, and subtracting from <math>2^{10} = 1024</math> gives <math>1024 - 443 = \boxed{581}</math>. | ||
+ | == See also == | ||
+ | {{AIME box|year=2014|n=II|num-b=8|num-a=10}} | ||
− | + | [[Category:Intermediate Combinatorics Problems]] | |
+ | {{MAA Notice}} |
Revision as of 20:09, 20 May 2014
Contents
[hide]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 * 5c2 or 100 have 3 adjacent. With 6 chairs in the subset, 10 have all 6 adjacent, 10 * 3 or 30 have 5 adjacent, 10 * 4c2 or 60 have 4 adjacent, 10 * 3 / 2 or 15 have 2 groups of 3 adjacent chairs, and 10 * (5c2 - 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 10c7 or 120, 10c8 or 45, 10c9 or 10, and 10c10 or 1. Adding, we get 10 + 10 + 50 + 10 + 40 + 100 + 10 + 30 + 60 + 15 + 70 + 120 + 45 + 10 + 1 = 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 , as confirmed above. This claim can be verified by PIE: there are ways to arrange 3 adjacent chairs, but then we subtract 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 = .
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 , where 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 (representing the cases when the first, second, and/or third chair is occupied). Also, , and hence . Now we know the complement is , and subtracting from gives .
See also
2014 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 8 |
Followed by Problem 10 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.