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. 
