Difference between revisions of "2015 AMC 10A Problems/Problem 22"
(Added solution) |
Eggynornor (talk | contribs) m (→Solution 5) |
||
Line 63: | Line 63: | ||
Case <math>3:</math> <math>2</math> people are standing. To do this, we imagine having 6 people with tails in a line first. Notate "tails" with <math>T</math>. Thus, we have <math>TTTTTT</math>. Now, we look to distribute the 2 <math>H</math>'s into the 7 gaps made by the <math>T</math>'s. We can do this in <math>{7 \choose 2}</math> ways. However, note one way does not work, because we have two H's at the end, and the problem states we have a table, not a line. So, we have <math>{7 \choose 2}-1=20</math> arrangements. | Case <math>3:</math> <math>2</math> people are standing. To do this, we imagine having 6 people with tails in a line first. Notate "tails" with <math>T</math>. Thus, we have <math>TTTTTT</math>. Now, we look to distribute the 2 <math>H</math>'s into the 7 gaps made by the <math>T</math>'s. We can do this in <math>{7 \choose 2}</math> ways. However, note one way does not work, because we have two H's at the end, and the problem states we have a table, not a line. So, we have <math>{7 \choose 2}-1=20</math> arrangements. | ||
− | Case <math>4:</math> <math>3</math> people are standing. Similarly, we imagine 5 <math>T</math>'s. Thus, we have <math>TTTTT</math>. We distribute 3 <math>H</math>'s into the gaps, which can be done <math>{6 \choose 3}</math> ways. However, 4 arrangements will not work. (See this by putting the H's at the ends, and then choosing one of the remaining 4 gaps: <math>{4 \choose 1}</math> | + | Case <math>4:</math> <math>3</math> people are standing. Similarly, we imagine 5 <math>T</math>'s. Thus, we have <math>TTTTT</math>. We distribute 3 <math>H</math>'s into the gaps, which can be done <math>{6 \choose 3}</math> ways. However, 4 arrangements will not work. (See this by putting the H's at the ends, and then choosing one of the remaining 4 gaps: <math>{4 \choose 1}=4</math>) Thus, we have <math>{6 \choose 3}-4=16</math> arrangements. |
Case <math>5:</math> <math>4</math> people are standing. This can clearly be done in 2 ways: <math>HTHTHTHT</math> or <math>THTHTHTH</math>. This yields <math>2</math> arrangements. | Case <math>5:</math> <math>4</math> people are standing. This can clearly be done in 2 ways: <math>HTHTHTHT</math> or <math>THTHTHTH</math>. This yields <math>2</math> arrangements. |
Revision as of 00:02, 27 November 2019
- The following problem is from both the 2015 AMC 12A #17 and 2015 AMC 10A #22, so both problems redirect to this page.
Contents
[hide]Problem
Eight people are sitting around a circular table, each holding a fair coin. All eight people flip their coins and those who flip heads stand while those who flip tails remain seated. What is the probability that no two adjacent people will stand?
Solution
Solution 1
We count how many valid arrangements there are and then divide by .
First, arbitrarily pick a person A and consider whether he is standing or sitting. If he is sitting, then the number of valid arrangements is the same as the number of valid arrangements of 7 people in a line. If he is standing, then the two people next to him must be sitting, so the number of valid arrangements is the same as the number of valid arrangements of 5 people in a line.
Let denote the number of ways to arrange
people in a line such that no two adjacent people are standing. We determine a recurrence relation for
as follows. If the first person in the line is standing, then the next person must be sitting, and there are
ways to arrange the rest. If the first person in the line is sitting, then there are
ways to arrange the rest. Thus,
and using the fact that
and
, we get that
is the
nd Fibonacci number
. In particular,
and
.
So our desired count is , and the answer is
.
Solution 2
We will count how many valid standing arrangements there are (counting rotations as distinct), and divide by at the end. We casework on how many people are standing.
Case
people are standing. This yields
arrangement.
Case
person is standing. This yields
arrangements.
Case
people are standing. This yields
arrangements, because the two people cannot be next to each other.
Case
people are standing. Then the people must be arranged in stand-sit-stand-sit-stand-sit-stand-sit fashion, yielding
possible arrangements.
More difficult is:
Case
people are standing. First, choose the location of the first person standing (
choices). Next, choose
of the remaining people in the remaining
legal seats to stand, amounting to
arrangements considering that these two people cannot stand next to each other. However, we have to divide by
because there are
ways to choose the first person given any three. This yields
arrangements for Case
Alternate Case Use complementary counting. Total number of ways to choose 3 people from 8 which is
. Sub-case
three people are next to each other which is
. Sub-case
two people are next to each other and the third person is not
. This yields
Summing gives and so our probability is
.
Solution 3
We will count how many valid standing arrangements there are counting rotations as distinct and divide by at the end.
Line up all
people linearly. In order for no two people standing to be adjacent, we will place a sitting person to the right of each standing person. In effect, each standing person requires
spaces and the standing people are separated by sitting people. We just need to determine the number of combinations of pairs and singles and the problem becomes very similar to pirates and gold aka stars and bars aka sticks and stones aka balls and urns.
If there are standing, there are
ways to place them.
For
there are
ways.
etc.
Summing, we get
ways.
Now we consider that the far right person can be standing as well, so we have
ways
Together we have , and so our probability is
.
Solution 4
We will count how many valid standing arrangements there are (counting rotations as distinct), and divide by at the end. If we suppose for the moment that the people are in a line, and decide from left to right whether they sit or stand. If the leftmost person sits, we have the same number of arrangements as if there were only
people. If they stand, we count the arrangements with
instead because the person second from the left must sit. We notice that this is the Fibonacci sequence, where with
person there are two ways and with
people there are three ways. Carrying out the Fibonacci recursion until we get to
people, we find there are
standing arrangements. Some of these were illegal however, since both the first and last people stood. In these cases, both the leftmost and rightmost two people are fixed, leaving us to subtract the number of ways for
people to stand in a line, which is
from our sequence. Therefore our probability is
Solution 5
We will count the number of valid arrangements and then divide by at the end. We proceed with casework on how many people are standing.
Case
people are standing. This yields
arrangement.
Case
person is standing. This yields
arrangements.
Case
people are standing. To do this, we imagine having 6 people with tails in a line first. Notate "tails" with
. Thus, we have
. Now, we look to distribute the 2
's into the 7 gaps made by the
's. We can do this in
ways. However, note one way does not work, because we have two H's at the end, and the problem states we have a table, not a line. So, we have
arrangements.
Case
people are standing. Similarly, we imagine 5
's. Thus, we have
. We distribute 3
's into the gaps, which can be done
ways. However, 4 arrangements will not work. (See this by putting the H's at the ends, and then choosing one of the remaining 4 gaps:
) Thus, we have
arrangements.
Case
people are standing. This can clearly be done in 2 ways:
or
. This yields
arrangements.
Summing the cases, we get arrangements.
Thus, the probability is
See Also
2015 AMC 10A (Problems • Answer Key • Resources) | ||
Preceded by Problem 21 |
Followed by Problem 23 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | ||
All AMC 10 Problems and Solutions |
2015 AMC 12A (Problems • Answer Key • Resources) | |
Preceded by Problem 16 |
Followed by Problem 18 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
All AMC 12 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.