Difference between revisions of "2014 AIME II Problems/Problem 9"
(→Solution 3 (Complementary Counting)) |
(→Solution 1 (Casework)) |
||
| Line 3: | Line 3: | ||
==Solution 1 (Casework)== | ==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 * | + | We know that a subset with less than <math>3</math> chairs cannot contain <math>3</math> adjacent chairs. There are only <math>10</math> sets of <math>3</math> chairs so that they are all <math>3</math> adjacent. There are <math>10</math> subsets of <math>4</math> chairs where all <math>4</math> are adjacent, and <math>10 * 5</math> or <math>50</math> where there are only <math>3.</math> If there are <math>5</math> chairs, <math>10</math> have all <math>5</math> adjacent, <math>10 * 4</math> or <math>40</math> have <math>4</math> adjacent, and <math>10 * {5\choose 2}</math> or <math>100</math> have <math>3</math> adjacent. With <math>6</math> chairs in the subset, <math>10</math> have all <math>6</math> adjacent, <math>10(3)</math> or <math>30</math> have <math>5</math> adjacent, <math>10 * {4\choose2}</math> or <math>60</math> have <math>4</math> adjacent, <math>\frac{10 * 3}{2}</math> or <math>15</math> have <math>2</math> groups of <math>3</math> adjacent chairs, and <math>10 * ({5\choose2} - 3)</math> or <math>70</math> have <math>1</math> group of <math>3</math> adjacent chairs. All possible subsets with more than <math>6</math> chairs have at least <math>1</math> group of <math>3</math> adjacent chairs, so we add <math>{10\choose7}</math> or <math>120</math>, <math>{10\choose8}</math> or <math>45</math>, <math>{10\choose9}</math> or <math>10</math>, and <math>{10\choose10}</math> or <math>1.</math> Adding, we get <math>10 + 10 + 50 + 10 + 40 + 100 + 10 + 30 + 60 + 15 + 70 + 120 + 45 + 10 + 1 = \boxed{581}.</math> |
==Solution 2 (PIE)== | ==Solution 2 (PIE)== | ||
Revision as of 20:17, 20 May 2014
Contents
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 
chairs cannot contain adjacent chairs. There are only 
sets of chairs so that they are all adjacent. There are subsets of 
chairs where all are adjacent, and 
or 
where there are only 
If there are 
chairs, have all adjacent, 
or 
have adjacent, and 
or 
have adjacent. With 
chairs in the subset, have all adjacent, 
or 
have adjacent, 
or 
have adjacent, 
or 
have 
groups of adjacent chairs, and 
or 
have 
group of adjacent chairs. All possible subsets with more than chairs have at least group of adjacent chairs, so we add 
or 
, 
or 
, 
or , and 
or 
Adding, we get 
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. 
