Difference between revisions of "2015 AMC 10A Problems/Problem 22"
Mathpro12345 (talk | contribs) (→Solution 1) |
Jacoporizzo (talk | contribs) (→Solutions) |
||
(3 intermediate revisions by 2 users not shown) | |||
Line 7: | Line 7: | ||
==Solutions== | ==Solutions== | ||
− | ===Solution | + | ===Solution 1=== |
We will count how many valid standing arrangements there are (counting rotations as distinct), and divide by <math>2^8 = 256</math> at the end. We casework on how many people are standing. | We will count how many valid standing arrangements there are (counting rotations as distinct), and divide by <math>2^8 = 256</math> at the end. We casework on how many people are standing. | ||
Line 26: | Line 26: | ||
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>. | ||
− | ===Solution | + | ===Solution 2=== |
We will count how many valid standing arrangements there are counting rotations as distinct and divide by <math>256</math> at the end. | We will count how many valid standing arrangements there are counting rotations as distinct and divide by <math>256</math> at the end. | ||
Line up all <math>8</math> 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 <math>2</math> 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. | Line up all <math>8</math> 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 <math>2</math> 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. | ||
Line 40: | Line 40: | ||
Together we have <math>34+13=47</math>, and so our probability is <math>\boxed{\textbf{(A) } \dfrac{47}{256}}</math>. | Together we have <math>34+13=47</math>, and so our probability is <math>\boxed{\textbf{(A) } \dfrac{47}{256}}</math>. | ||
− | ===Solution | + | === Solution 3 (Recursion) === |
− | + | Because the denominator is always <math>256</math>, we can count the numerator with a recursion. Define <math>a_n</math> and <math>b_n</math> as the number of satisfying arrangements on a circle and row with <math>n</math> seats, respectively. Then, observe that <cmath>a_n=b_{n-1}+b_{n-3}</cmath> <cmath>b_n=b_{n-1}+b_{n-2}</cmath> (From casework on whether the nth position is <math>H,T</math>). Because <math>b_1=2, b_2=3</math>, we can continue to write out each <math>b_i</math> and hence find <math>a_8=47</math>. Our answer is then <math>\boxed{\textbf{(A) } \dfrac{47}{256}}</math>. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
=== Video Solution by Richard Rusczyk === | === Video Solution by Richard Rusczyk === | ||
Latest revision as of 15:34, 27 January 2021
- 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?
Solutions
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 .
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 .
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.