AMC 10 · 2008 · #22

Grade 7 probability
probability-basictree-enumerationparity systematic-enumerationcasework ↑ Prerequisites: probability-basic
📏 Medium solution 💡 2 insights
Problem
Jacob builds a sequence. The first term is 6. To get each next term he flips a fair coin: heads means double the current term and subtract 1; tails means halve the current term and subtract 1. Find the probability that the fourth term is an integer.

Pick an answer.

(A)
$\ \frac{1}{6}$
(B)
$\ \frac{1}{3}$
(C)
$\ \frac{1}{2}$
(D)
$\ \frac{5}{8}$
(E)
$\ \frac{3}{4}$

AMC 10 2008 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve
Strategy Draw a Diagram

Only 3 flips ever happen, so there are just 8 possible paths. A branching tree diagram lays out every path and the fourth term it produces, so we can simply count how many of those land on a whole number.

1STEP 1

Count the paths

Three flips separate term 1 from term 4, each with two outcomes, so there are 8 equally likely paths.

2³ = 8
2STEP 2

Write the two rules

Let x be the current term: heads sends it to 2x12x-1 and tails sends it to x21\frac{x}{2}-1.

H: x → 2x - 1, T: x → x/2 - 1
3STEP 3

Grow the tree

Apply both rules at every level: 6 branches to 11 and 2, then to 21, 4.5, 3, 0, then to eight fourth terms.

6 → {11, 2} → {21, 4.5, 3, 0} → {41, 9.5, 8, 1.25, 5, 0.5, -1, -1}
4STEP 4

Count integer endings

In flip order the fourth terms are 41, 9.5, 8, 1.25, 5, 0.5, -1, -1, and 5 of them are integers.

{41, 8, 5, -1, -1} → 5 integers out of 8
5STEP 5

Form the probability

Divide integer paths by all paths: the probability is 58\frac{5}{8}, which is choice (D).

P = 5/8
Answer
5/8
5/8 sits between 1/2 and 3/4, which fits the picture: a bit more than half the paths work. A shortcut confirms the count. Every term-3 value here (21, 4.5, 3, 0) is a multiple of 1/2, so a final heads (2x - 1) always lands on an integer, covering 4 paths. The only tails ending that is an integer comes from the path tails-tails, which reaches 0, since 0/2 - 1 = -1. That adds 1 more path, giving 5 in all, matching the tree count.
💡Key takeaway

When only a few coin flips can happen, draw the whole tree and just count the branches you want.

  • Count the paths
  • Write the two rules
  • Grow the tree
  • Count integer endings
  • Form the probability