Difference between revisions of "2014 AIME II Problems/Problem 9"
(→Solution 3 (Complementary Counting)) |
|||
(11 intermediate revisions by 6 users not shown) | |||
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 | + | 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 \cdot 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 \cdot 4</math> or <math>40</math> have <math>4</math> adjacent, and <math>10 \cdot {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 \cdot {4\choose2}</math> or <math>60</math> have <math>4</math> adjacent, <math>\frac{10 \cdot 3}{2}</math> or <math>15</math> have <math>2</math> groups of <math>3</math> adjacent chairs, and <math>10 \cdot \left({5\choose2} - 3\right)</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)== | ||
Starting with small cases, we see that four chairs give <math>4 + 1 = 5</math>, five chairs give <math>5 + 5 + 1 = 11</math>, and six chairs give <math>6 + 6 + 6 + 6 + 1 = 25.</math> Thus, n chairs should give <math>n 2^{n-4} + 1</math>, as confirmed above. This claim can be verified by the principle of inclusion-exclusion: there are <math>n 2^{n-3}</math> ways to arrange <math>3</math> adjacent chairs, but then we subtract <math>n 2^{n-4}</math> ways to arrange <math>4.</math> Finally, we add <math>1</math> to account for the full subset of chairs. Thus, for <math>n = 10</math> we get a first count of <math>641.</math> | Starting with small cases, we see that four chairs give <math>4 + 1 = 5</math>, five chairs give <math>5 + 5 + 1 = 11</math>, and six chairs give <math>6 + 6 + 6 + 6 + 1 = 25.</math> Thus, n chairs should give <math>n 2^{n-4} + 1</math>, as confirmed above. This claim can be verified by the principle of inclusion-exclusion: there are <math>n 2^{n-3}</math> ways to arrange <math>3</math> adjacent chairs, but then we subtract <math>n 2^{n-4}</math> ways to arrange <math>4.</math> Finally, we add <math>1</math> to account for the full subset of chairs. Thus, for <math>n = 10</math> we get a first count of <math>641.</math> | ||
− | However, we overcount cases in which there are two distinct groups of three or more chairs. | + | However, we overcount cases in which there are two distinct groups of three or more chairs. We have <math>5</math> cases for two groups of <math>3</math> directly opposite each other, <math>5</math> for two groups of four, <math>20</math> for two groups of <math>3</math> not symmetrically opposite, <math>20</math> for a group of <math>3</math> and a group of <math>4</math>, and <math>10</math> for a group of <math>3</math> and a group of <math>5.</math> Thus, we have <math>641 - 60 = \boxed{581}</math>. |
− | ==Solution 3 (Complementary Counting)== | + | ==Solution 3 (Complementary Counting and Recursion)== |
− | It is possible to use recursion to count the complement. Number the chairs <math>1, 2, 3, ..., 10.</math> If chair <math>1</math> is not occupied, then we have a line of <math>9</math> chairs such that there is no consecutive group of three. If chair <math>1</math> is occupied, then we split into more cases. If chairs <math>2</math> and <math>10</math> are empty, then we have a line of <math>7.</math> If chair <math>2</math> is empty but chair <math>10</math> is occupied, then we have a line of <math>6</math> chairs (because chair <math>9</math> cannot be occupied); this is similar to when chair <math>2</math> is occupied and chair <math>10</math> is empty. Finally, chairs <math>2</math> and <math>10</math> cannot be simultaneously occupied. Thus, we have reduced the problem down to computing <math>T_9 + T_7 + 2T_6</math>, where <math>T_n</math> counts the ways to select a subset of chairs | + | It is possible to use recursion to count the complement. Number the chairs <math>1, 2, 3, ..., 10.</math> If chair <math>1</math> is not occupied, then we have a line of <math>9</math> chairs such that there is no consecutive group of three. If chair <math>1</math> is occupied, then we split into more cases. If chairs <math>2</math> and <math>10</math> are empty, then we have a line of <math>7.</math> If chair <math>2</math> is empty but chair <math>10</math> is occupied, then we have a line of <math>6</math> chairs (because chair <math>9</math> cannot be occupied); this is similar to when chair <math>2</math> is occupied and chair <math>10</math> is empty. Finally, chairs <math>2</math> and <math>10</math> cannot be simultaneously occupied. Thus, we have reduced the problem down to computing <math>T_9 + T_7 + 2T_6</math>, where <math>T_n</math> counts the ways to select a subset of chairs <math>\textit{in a line}</math> from a group of n chairs such that there is no group of <math>3</math> chairs in a row. |
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 unoccupied). 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 unoccupied). 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>. | ||
+ | ==Solution 4== | ||
+ | Let's calculate the complement. As mentioned in solution <math>3</math>, the number of ways to have a subset <math>n</math> chairs in a line with no 3 consectuive chairs satisfies <math>T_n = T_{n-1} + T_{n-2} + T_{n-3}</math>. Setting <math>T_{1} = 2, T_{2} = 4</math>, and <math>T_{3} = 7</math>, we get that <math>T_{10} = 504</math>. Since this is in a line and not a circle, we must subtract the cases that would include 3 consecutive chairs if the endpoints of the line were put together. If chairs <math>1</math>, <math>2</math> and <math>10</math> are in the subset, that would not work. The same goes for if chairs <math>1</math>, <math>9</math> and <math>10</math> were in the subset. If chairs <math>1</math>, <math>2</math> and <math>10</math> are in the set then chair <math>3</math> must not be in the set. However, chair <math>9</math> could be in or not in the set because we only want to count what cases where no <math>3</math> chairs are consecutive in the line but there would be consecutive chairs in a circle. If chair <math>9</math> is not included, there are <math>T_{5} = 24</math> ways. If chair <math>9</math> is in the set then there are <math>T_{4} = 13</math> ways. So we must subtract <math>2 \cdot (24 + 13) = 74</math> However we are counting the case where chairs <math>1</math>, <math>2</math>, <math>9</math> and <math>10</math> are included twice. So we only have to subtract <math>74 - 13 = 61</math>. <math>504 - 61 = 443</math>. This entire time we were calculating the complement so <math>2^{10} - 443 = \fbox{581}</math> | ||
+ | |||
+ | ~sdfgfjh | ||
== See also == | == See also == | ||
{{AIME box|year=2014|n=II|num-b=8|num-a=10}} | {{AIME box|year=2014|n=II|num-b=8|num-a=10}} |
Latest revision as of 15:41, 14 September 2024
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 , 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. 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 .
Solution 3 (Complementary Counting and Recursion)
It is possible to use recursion to count the complement. Number the chairs If chair is not occupied, then we have a line of chairs such that there is no consecutive group of three. If chair is occupied, then we split into more cases. If chairs and are empty, then we have a line of If chair is empty but chair is occupied, then we have a line of chairs (because chair cannot be occupied); this is similar to when chair is occupied and chair is empty. Finally, chairs and 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 chairs in a row.
Now, we notice that (representing the cases when the first, second, and/or third chair is unoccupied). Also, , and hence . Now we know the complement is , and subtracting from gives .
Solution 4
Let's calculate the complement. As mentioned in solution , the number of ways to have a subset chairs in a line with no 3 consectuive chairs satisfies . Setting , and , we get that . Since this is in a line and not a circle, we must subtract the cases that would include 3 consecutive chairs if the endpoints of the line were put together. If chairs , and are in the subset, that would not work. The same goes for if chairs , and were in the subset. If chairs , and are in the set then chair must not be in the set. However, chair could be in or not in the set because we only want to count what cases where no chairs are consecutive in the line but there would be consecutive chairs in a circle. If chair is not included, there are ways. If chair is in the set then there are ways. So we must subtract However we are counting the case where chairs , , and are included twice. So we only have to subtract . . This entire time we were calculating the complement so
~sdfgfjh
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.