Difference between revisions of "2014 AIME II Problems/Problem 9"
(→Solution 3 (Complementary Counting)) |
Mathkiddie (talk | contribs) (→Solution 2 (PIE)) |
||
(14 intermediate revisions by 10 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 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 | + | 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>. |
== See also == | == See also == |
Latest revision as of 16:16, 7 June 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
.
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.