Difference between revisions of "2014 AIME II Problems/Problem 9"
m (→Solution 1 (Casework)) |
|||
Line 3: | Line 3: | ||
==Solution 1 (Casework)== | ==Solution 1 (Casework)== | ||
− | 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 + | + | 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 23:38, 14 July 2015
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 , five chairs give , and six chairs give Thus, n chairs should give , as confirmed above. This claim can be verified by the principle of inclusion-exclusion: there are ways to arrange adjacent chairs, but then we subtract ways to arrange Finally, we add to account for the full subset of chairs. Thus, for we get a first count of
However, we overcount cases in which there are two distinct groups of three or more chairs. Time to casework: we have cases for two groups of directly opposite each other, for two groups of four, for two groups of not symmetrically opposite, for a group of and a group of , and for a group of and a group of Thus, we have .
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.