1990 AIME Problem 9

Attempt Problem 9 of the 1990 AIME below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 1990 AIME solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

9.

A fair coin is to be tossed 1010 times. Let ij,\frac{i}{j}, in lowest terms, be the probability that heads never occur on consecutive tosses. Find i+j.i+j.

Answer: 73
Concepts:recursive countingFibonaccibasic probability
Difficulty rating: 2000
Small Hint:

Count valid length-nn toss strings according to whether they end in tails or heads

Big Hint:

The resulting recurrence is Fibonacci-like, with initial counts 22 and 33

Solution:

Let unu_n be the number of length-nn toss strings with no consecutive heads. A valid string ending in tails is obtained by appending T\mathrm{T} to any valid length-(n1)(n-1) string, while one ending in heads is obtained by appending TH\mathrm{TH} to any valid length-(n2)(n-2) string. Hence un=un1+un2,u_n=u_{n-1}+u_{n-2}, with u1=2u_1=2 and u2=3.u_2=3. This gives u10=144.u_{10}=144. The probability is 144210=964,\frac{144}{2^{10}}=\frac{9}{64}, so i+j=9+64=73.i+j=9+64=73.

← Problem 8#8
Full Exam

Problem 9 in Other Years