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 * 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>
+
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. Time to casework: 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>.
+
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 [i]in a line[/i] from a group of n chairs such that there is no group of <math>3</math> chairs in a row.
+
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

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 \cdot 5$ or $50$ where there are only $3.$ If there are $5$ chairs, $10$ have all $5$ adjacent, $10 \cdot 4$ or $40$ have $4$ adjacent, and $10 \cdot {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 \cdot {4\choose2}$ or $60$ have $4$ adjacent, $\frac{10 \cdot 3}{2}$ or $15$ have $2$ groups of $3$ adjacent chairs, and $10 \cdot \left({5\choose2} - 3\right)$ 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, n chairs should give $n 2^{n-4} + 1$, as confirmed above. This claim can be verified by the principle of inclusion-exclusion: 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. 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 and Recursion)

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); this is similar to when chair $2$ is occupied and chair $10$ is 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 $\textit{in a line}$ 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 unoccupied). 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}$.

Solution 4

Let's calculate the complement. As mentioned in solution $3$, the number of ways to have a subset $n$ chairs in a line with no 3 consectuive chairs satisfies $T_n = T_{n-1} + T_{n-2} + T_{n-3}$. Setting $T_{1} = 2, T_{2} = 4$, and $T_{3} = 7$, we get that $T_{10} = 504$. 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 $1$, $2$ and $10$ are in the subset, that would not work. The same goes for if chairs $1$, $9$ and $10$ were in the subset. If chairs $1$, $2$ and $10$ are in the set then chair $3$ must not be in the set. However, chair $9$ could be in or not in the set because we only want to count what cases where no $3$ chairs are consecutive in the line but there would be consecutive chairs in a circle. If chair $9$ is not included, there are $T_{5} = 24$ ways. If chair $9$ is in the set then there are $T_{4} = 13$ ways. So we must subtract $2 \cdot (24 + 13) = 74$ However we are counting the case where chairs $1$, $2$, $9$ and $10$ are included twice. So we only have to subtract $74 - 13 = 61$. $504 - 61 = 443$. This entire time we were calculating the complement so $2^{10} - 443 = \fbox{581}$

~sdfgfjh

See also

2014 AIME II (ProblemsAnswer KeyResources)
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. AMC logo.png