2008 AMC 10A Problem 22

Question

Jacob uses the following procedure to write down a sequence of numbers. First he chooses the first term to be

6.

To generate each succeeding term, he flips a fair coin. If it comes up heads, he doubles the previous term and subtracts

1.

If it comes up tails, he takes half of the previous term and subtracts

1.

What is the probability that the fourth term in Jacob’s sequence is an integer?

\dfrac{1}{6}

\dfrac{1}{3}

\dfrac{1}{2}

\dfrac{5}{8}

\dfrac{3}{4}

Build a tree of the possible sequences; each flip splits into two branches

Track which fourth terms are integers, remembering that halving an odd number breaks integrality

Starting from

6,

the second terms are

11

(heads) and

2

(tails).

Continuing the tree, the eight equally likely fourth terms are

41, 9.5, 8, 1.25, 5, 0.5, -1, -1.

Of these,

41, 8, 5, -1, -1

are integers, so the probability is

\dfrac{5}{8}.

Thus, the correct answer is D.

Problem 22 in other years