Mock AIME 1 2007-2008 Problems/Problem 8
Problem
A sequence of ten s and/or
s is randomly generated. If the probability that the sequence does not contain two consecutive
s can be written in the form
, where
are relatively prime positive integers, find
.
Solution
Let denote the number of sequences of length
that do not contain consecutive
s. A sequence of length
must either end in a
or a
. If the string of length
ends in a
, this string could have been formed by appending a
to any sequence of length
, of which there are
such strings. If the string of length
ends in a
, this string could have been formed by appending a
(to avoid consecutive
s) to any sequence of length
, of which there are
such strings. Thus, we have the recursion
Solving for initial conditions, we find
. Thus we have the Fibonacci sequence with shifted indices; indeed
, so
. The probability is
, and
.
See also
Mock AIME 1 2007-2008 (Problems, Source) | ||
Preceded by Problem 7 |
Followed by Problem 9 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 |