Difference between revisions of "1990 AIME Problems/Problem 9"
m (→Solution) |
(→Solution 1) |
||
(8 intermediate revisions by 5 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | A [[fair]] coin is to be tossed <math>10_{}^{}</math> times. Let <math>i | + | A [[fair]] coin is to be tossed <math>10_{}^{}</math> times. Let <math>\frac{i}{j}^{}_{}</math>, in lowest terms, be the [[probability]] that heads never occur on consecutive tosses. Find <math>i+j_{}^{}</math>. |
__TOC__ | __TOC__ | ||
+ | |||
== Solution == | == Solution == | ||
=== Solution 1 === | === Solution 1 === | ||
Line 11: | Line 12: | ||
:<math>(H)\ T\ (H)\ T\ (H)\ T\ (H)\ T\ (H)\ T\ (H)</math> | :<math>(H)\ T\ (H)\ T\ (H)\ T\ (H)\ T\ (H)\ T\ (H)</math> | ||
− | There are six slots for the heads to be placed, but only <math>5</math> heads remaining. Thus, using [[stars-and-bars]] there are <math>{6\choose5}</math> possible combinations of | + | There are six slots for the heads to be placed, but only <math>5</math> heads remaining. Thus, using [[stars-and-bars]] there are <math>{6\choose5}</math> possible combinations of <math>5</math> heads. Continuing this pattern, we find that there are <math>\sum_{i=6}^{11} {i\choose{11-i}} = {6\choose5} + {7\choose4} + {8\choose3} + {9\choose2} + {{10}\choose1} + {{11}\choose0} = 144</math>. There are a total of <math>2^{10}</math> possible flips of <math>10</math> coins, making the probability <math>\frac{144}{1024} = \frac{9}{64}</math>. Thus, our solution is <math>9 + 64 = \boxed{073}</math>. |
− | === Solution 2 === | + | === Solution 2 (Recursion)=== |
Call the number of ways of flipping <math>n</math> coins and not receiving any consecutive heads <math>S_n</math>. Notice that tails must be received in at least one of the first two flips. | Call the number of ways of flipping <math>n</math> coins and not receiving any consecutive heads <math>S_n</math>. Notice that tails must be received in at least one of the first two flips. | ||
Line 56: | Line 57: | ||
{{AIME box|year=1990|num-b=8|num-a=10}} | {{AIME box|year=1990|num-b=8|num-a=10}} | ||
{{MAA Notice}} | {{MAA Notice}} | ||
+ | |||
+ | [[Category:Intermediate Combinatorics Problems]] |
Latest revision as of 14:03, 24 June 2024
Problem
A fair coin is to be tossed times. Let , in lowest terms, be the probability that heads never occur on consecutive tosses. Find .
Contents
[hide]Solution
Solution 1
Clearly, at least tails must be flipped; any less, then by the Pigeonhole Principle there will be heads that appear on consecutive tosses.
Consider the case when tails occur. The heads must fall between the tails such that no two heads fall between the same tails, and must fall in the positions labeled :
There are six slots for the heads to be placed, but only heads remaining. Thus, using stars-and-bars there are possible combinations of heads. Continuing this pattern, we find that there are . There are a total of possible flips of coins, making the probability . Thus, our solution is .
Solution 2 (Recursion)
Call the number of ways of flipping coins and not receiving any consecutive heads . Notice that tails must be received in at least one of the first two flips.
If the first coin flipped is a T, then the remaining flips must fall under one of the configurations of .
If the first coin flipped is a H, then the second coin must be a T. There are then configurations.
Thus, . By counting, we can establish that and . Therefore, , forming the Fibonacci sequence. Listing them out, we get , and the 10th number is . Putting this over to find the probability, we get . Our solution is .
Solution 3
We can also split the problem into casework.
Case 1: 0 Heads
There is only one possibility.
Case 2: 1 Head
There are 10 possibilities.
Case 3: 2 Heads
There are 36 possibilities.
Case 4: 3 Heads
There are 56 possibilities.
Case 5: 4 Heads
There are 35 possibilities.
Case 6: 5 Heads
There are 6 possibilities.
We have , and there are possible outcomes, so the probability is , and the answer is .
See also
1990 AIME (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.