2008 AMC 10A Problem 22

P21-25~5 minPrint

Basic Probability Number Properties Sequences & Series Organized listing / direct enumeration

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?

Show solution without answering

Key insight

Only three coin flips matter, so list all eight paths and follow the actual numbers. Five of the eight fourth terms are whole numbers.

Solution

1. The first term is $6$ with no flip. The second, third and fourth terms each need one flip, so there are three flips and $2 \times 2 \times 2 = 8$ equally likely ways they can go.
2. Eight cases is few enough to list. Write H for heads (double, then subtract $1$ ) and T for tails (halve, then subtract $1$ ). Follow the numbers from $6$ .
3. Second term. H: $2 \times 6 - 1 = 11$ . T: $6 \div 2 - 1 = 2$ .
4. Third term.
- From $11$ : H gives $21$ ; T gives $5.5 - 1 = 4.5$ .
- From $2$ : H gives $3$ ; T gives $1 - 1 = 0$ .
5. Fourth term.

Path	Fourth term	Whole number?
H H H	$2 \times 21 - 1 = 41$	yes
H H T	$10.5 - 1 = 9.5$	no
H T H	$2 \times 4.5 - 1 = 8$	yes
H T T	$2.25 - 1 = 1.25$	no
T H H	$2 \times 3 - 1 = 5$	yes
T H T	$1.5 - 1 = 0.5$	no
T T H	$2 \times 0 - 1 = -1$	yes
T T T	$0 - 1 = -1$	yes

Five of the eight paths end at a whole number, so the probability is $\frac{5}{8}$ .

The answer is $\boxed{\textbf{(D)}\ \frac{5}{8}}$ .

Why this works

With only eight cases, a neat list is faster and safer than a clever shortcut. Keep the real numbers, not just "whole or not": doubling can turn a half, like $4.5$ , back into a whole number. A table with one row per path makes sure no case is missed.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

The first term needs no flip, so the fourth term is determined by three flips: $2^3 = 8$ equally likely sequences. Write $H$ for "double, then subtract $1$ " and $T$ for "halve, then subtract $1$ ," and trace every path from $6$ .

After flip 1: $H \to 11$ , $T \to 2$ .

After flip 2:
- from $11$ : $H \to 21$ , $T \to 4.5$ ;
- from $2$ : $H \to 3$ , $T \to 0$ .

After flip 3:
- from $21$ : $H \to 41$ , $T \to 9.5$ ;
- from $4.5$ : $H \to 8$ , $T \to 1.25$ ;
- from $3$ : $H \to 5$ , $T \to 0.5$ ;
- from $0$ : $H \to -1$ , $T \to -1$ .

The eight fourth terms are $41,\ 9.5,\ 8,\ 1.25,\ 5,\ 0.5,\ -1,\ -1$ . Five of them are integers.

The probability is $\frac{5}{8}$ , so the answer is $\boxed{\textbf{(D)}\ \frac{5}{8}}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 7: Introduction to Probability
Introduction to Number Theory, Chapter 1: Integers: The Basics
Introduction to Algebra, Chapter 21: Sequences & Series (§21.1, §21.2, §21.3, §21.4)
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.2)