1990 AIME Problems/Problem 9
Problem
A fair coin is to be tossed times. Let
, in lowest terms, be the probability that heads never occur on consecutive tosses. Find
.
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 5 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
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
.
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.