Difference between revisions of "2015 AMC 10A Problems/Problem 22"
Isabelchen (talk | contribs) |
(→Solution 1) |
||
(6 intermediate revisions by 4 users not shown) | |||
Line 17: | Line 17: | ||
Case <math>3:</math> <math>2</math> people are standing. This yields <math>\dbinom{8}{2} - 8 = 20</math> arrangements, because the two people cannot be next to each other. | Case <math>3:</math> <math>2</math> people are standing. This yields <math>\dbinom{8}{2} - 8 = 20</math> arrangements, because the two people cannot be next to each other. | ||
− | Case <math> | + | Case <math>5:</math> <math>4</math> people are standing. Then the people must be arranged in stand-sit-stand-sit-stand-sit-stand-sit fashion, yielding <math>2</math> possible arrangements. |
More difficult is: | More difficult is: | ||
− | Case <math> | + | Case <math>4:</math> <math>3</math> people are standing. First, choose the location of the first person standing (<math>8</math> choices). Next, choose <math>2</math> of the remaining people in the remaining <math>5</math> legal seats to stand, amounting to <math>6</math> arrangements considering that these two people cannot stand next to each other. However, we have to divide by <math>3,</math> because there are <math>3</math> ways to choose the first person given any three. This yields <math>\dfrac{8 \cdot 6}{3} = 16</math> arrangements for Case <math>5.</math> |
− | Alternate Case <math> | + | Alternate Case <math>4:</math> Use complementary counting. Total number of ways to choose 3 people from 8 which is <math>\dbinom{8}{3}</math>. Sub-case <math>1:</math> three people are next to each other which is <math>\dbinom{8}{1}</math>. Sub-case <math>2:</math> two people are next to each other and the third person is not <math>\dbinom{8}{1}</math> <math>\dbinom{4}{1}</math>. This yields <math>\dbinom{8}{3} - \dbinom{8}{1} - \dbinom{8}{1} \dbinom{4}{1} = 16</math> |
Summing gives <math>1 + 8 + 20 + 2 + 16 = 47,</math> and so our probability is <math>\boxed{\textbf{(A) } \dfrac{47}{256}}</math>. | Summing gives <math>1 + 8 + 20 + 2 + 16 = 47,</math> and so our probability is <math>\boxed{\textbf{(A) } \dfrac{47}{256}}</math>. | ||
+ | |||
+ | Alternate: (Quicksolve) - We know that for case 5, there are 8 ways to choose the first person, and 3 ways to choose the first person given any 3 - which means that for the case, there is 8 * something divided by 3. The sum of the other cases is 31/256. Thus, add a multiple of 8 to 31 to get an answer. The options are 31 + 8 = 39, 31 + 16 = 47, 31 + 24 = 55, etc. The only possible answer is 47/256. | ||
==Solution 2== | ==Solution 2== | ||
Line 125: | Line 127: | ||
This sequence of numbers is called [https://en.wikipedia.org/wiki/Lucas_number Lucas Number]. | This sequence of numbers is called [https://en.wikipedia.org/wiki/Lucas_number Lucas Number]. | ||
− | ~isabelchen | + | ~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] |
+ | |||
+ | ==Solution 5 (Recursion)== | ||
+ | Note that there are <math>2^8=256</math> cases in total, so it suffices to find the number of satisfying cases. Define <math>h_n</math> and <math>t_n</math> as sequences of <math>h</math>’s and <math>t</math>’s where no <math>2</math> <math>h</math>’s are adjacent. The sequences will end in <math>h</math> and <math>t</math>, respectively (ignore the fact that they are in a circle for now). | ||
+ | |||
+ | In order for a sequence to end in <math>h</math>, the previous term has to be a <math>t</math>; a sequence with a length of <math>n</math> ending in <math>h</math> is equivalent to adding <math>h</math> to the end of a sequence of length <math>n-1</math> that ends with <math>t</math>. This means <math>h_n=t_{n-1}</math>. | ||
+ | |||
+ | In order for a sequence to end in <math>t</math>, the previous term can be <math>h</math> or <math>t</math>, so <math>t_n=t_{n-1}+h_{n-1}</math>. | ||
+ | |||
+ | Now, we have to take account of the circle. Notice that <math>t_n</math> does not depend on if the people are in a circle or not, but <math>h_n</math> does. To guarantee that some sequence that ends with <math>h</math> does not start with <math>h</math>, we have to add a <math>t</math> in the beginning of the sequence. Since there are <math>n-1</math> terms left, there are <math>h_{n-1}</math> sequences which end with <math>h</math> that satisfy the circle condition. | ||
+ | |||
+ | The length of our sequence is <math>8</math>, so we need to find <math>t_8+h_7</math>. Manipulating our recursions, we can find that <math>t_n=t_{n-1}+t_{n-1}</math>. Now, we proceed to find our terms. | ||
+ | |||
+ | <math>t_1=1</math> | ||
+ | |||
+ | <math>t_2=2</math> | ||
+ | |||
+ | <math>t_3=3</math> | ||
+ | |||
+ | <math>t_4=5</math> | ||
+ | |||
+ | <math>t_5=8</math> | ||
+ | |||
+ | <math>t_6=13</math> | ||
+ | |||
+ | <math>t_7=21</math> | ||
+ | |||
+ | <math>t_8=34</math> | ||
+ | |||
+ | Since <math>h_7=t_6</math> due to the fact that <math>h_n=t_{n-1}</math>, our answer is <math>\frac{34+13}{256}=\boxed{\textbf{(A) } \dfrac{47}{256}}</math>. | ||
+ | |||
+ | ~kn07 | ||
== Video Solution by Richard Rusczyk == | == Video Solution by Richard Rusczyk == |
Revision as of 01:26, 30 October 2023
- The following problem is from both the 2015 AMC 12A #17 and 2015 AMC 10A #22, so both problems redirect to this page.
Contents
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 1
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
.
Alternate: (Quicksolve) - We know that for case 5, there are 8 ways to choose the first person, and 3 ways to choose the first person given any 3 - which means that for the case, there is 8 * something divided by 3. The sum of the other cases is 31/256. Thus, add a multiple of 8 to 31 to get an answer. The options are 31 + 8 = 39, 31 + 16 = 47, 31 + 24 = 55, etc. The only possible answer is 47/256.
Solution 2
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 3 (Recursion)
Because the denominator is always , we can count the numerator with a recursion. Define
and
as the number of satisfying arrangements on a circle and row with
seats, respectively. Then, observe that
(From casework on whether the nth position is
). Because
, we can continue to write out each
and hence find
. Our answer is then
.
Solution 4 (Recursion)
We know that the denominator of the probability is . So now we only have to calculate the numerator, which is the number of arrangements for
people at a round table without
or more neighboring people standing.
Denote as number of arrangements for
people at a round table without
or more neighboring people standing. We can see that
,
, we are going to prove
We use to represent standing people, and
as sitting people. The problem becomes arranging
numbers of
or
around a circle with no consecutive
's.
We elect one person as the chairman, let him be , the first element in this circular sequence.
There are
cases to generate the arrangement of
numbers.
From the arrangement of
numbers, add
more number
counter-clockwise next to
.
If ,
is
, as the diagram shows:
If ,
is
,
could be
or
, as the diagram shows:
From the arrangement of
numbers, add
more numbers
and
counter-clockwise next to
.
If , then
, let
,
is
, as the diagram shows:
If , then
could be
or
. Let
,
is
, as the diagram shows:
From the above cases and the
diagrams, the arrangements of
are mutually exclusive collectively exhaustive, so
The answer is
This sequence of numbers is called Lucas Number.
Solution 5 (Recursion)
Note that there are cases in total, so it suffices to find the number of satisfying cases. Define
and
as sequences of
’s and
’s where no
’s are adjacent. The sequences will end in
and
, respectively (ignore the fact that they are in a circle for now).
In order for a sequence to end in , the previous term has to be a
; a sequence with a length of
ending in
is equivalent to adding
to the end of a sequence of length
that ends with
. This means
.
In order for a sequence to end in , the previous term can be
or
, so
.
Now, we have to take account of the circle. Notice that does not depend on if the people are in a circle or not, but
does. To guarantee that some sequence that ends with
does not start with
, we have to add a
in the beginning of the sequence. Since there are
terms left, there are
sequences which end with
that satisfy the circle condition.
The length of our sequence is , so we need to find
. Manipulating our recursions, we can find that
. Now, we proceed to find our terms.
Since due to the fact that
, our answer is
.
~kn07
Video Solution by Richard Rusczyk
https://www.youtube.com/watch?v=krlnSWWp0I0
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.