AMC 10 · 2008 · #17

Grade 7 number-theorycounting
Archetype Modular Cycle Frequency Count └ Sub-archetype Floor Count Across Residue Bins
parityrecursive-sequencemodular-arithmetic caseworkconvert-to-algebra ↑ Prerequisites: parity
📏 Medium solution 💡 2 insights
Problem
A sequence halves an even term and triples-plus-one an odd one. Count the starting values below a bound whose next three terms all exceed it.

Pick an answer.

(A)
250
(B)
251
(C)
501
(D)
502
(E)
1004
How to solve
Strategy Introduce a Variable

Which of the two rules fires at each step depends only on whether the current term is even or odd, never on how big it is. So the sequence's real state is a parity, and the whole question is how parity propagates for three steps. The first move is to find out which of the three inequalities actually carry information: two of them turn out to be free for every odd start, which means the problem is really one comparison, not three. That comparison hinges on a single yes-or-no question about a₃. Writing a₁ = 2m + 1 turns that question into a question about m, and answering it turns it into a question about a₁ modulo 4. The discipline that matters here is that the condition must come out both necessary and sufficient: ruling out the starts that fail is only half the job, and confirming that the survivors really do work is the other half.

1STEP 1

Even starts lose on move one

An even start loses on the very first move.

a₁ even → a₂ = a₁/2 ＜ a₁
2STEP 2

Two of the three come free

For an odd start, two of the three conditions come free.

a₂ - a₁ = 2a₁ + 1 ＞ 0, a₃ - a₁ = (3a₁+1)/2 - a₁ = (a₁+1)/2 ＞ 0
3STEP 3

Everything hinges on the parity of a₃

Everything hinges on the third term's parity.

a₃ even: a₁ - a₄ = a₁ - (3a₁+1)/4 = (a₁-1)/4 ≥ 0; a₃ odd: a₄ = 3a₃ + 1 ＞ a₃ ＞ a₁
4STEP 4

Name the odd start

Naming the odd start turns that into a remainder condition.

a₁ = 2m+1 → a₃ = (6m+4)/2 = 3m+2; a₃ odd ⇔ m odd ⇔ a₁ = 4k+3
5STEP 5

Count the qualifying starts

Counting those below the bound gives 502, choice (A).

4k+3 ≤ 2008 ⇔ k ≤ 2005/4 = 501.25 ⇔ 0 ≤ k ≤ 501 → 502 values
Answer
502
Check the small starts directly. 1 gives 4, 2, 1, so a₄ ties and fails. 2 gives 1 and fails immediately. 3 gives 10, 5, 16 and works. 4, 5, 6 fail (5 gives 16, 8, 4, and 4 is below 5). 7 gives 22, 11, 34 and works. So among 1 through 8 exactly 3 and 7 qualify: one start in four, which matches a count near a quarter of 2008. The distractors are each a specific bookkeeping slip, and naming them is the real check. 1004 is exactly the number of odd starts up to 2008, which is what a solver gets by stopping after a₂ and a₃ — step 2 showed those two inequalities are automatic, so 1004 is the answer to the wrong question. 501 is what the k-range gives if the k = 0 start a₁ = 3 is dropped, so the endpoint check in step 5 is what separates (C) from (D). 251 is the number of starts congruent to 7 modulo 8, which is what a solver gets by chasing the pattern one level too deep and demanding that a₃ satisfy the same remainder-3-mod-4 condition that a₁ does; 250 is that same over-chase off by one. One more caution: the tempting shortcut 'one quarter of the integers up to 2008, so 2008 divided by 4' lands on 502 only because 2008 happens to be a multiple of 4. The count that is safe for any bound is the k-range count used above.
💡Key takeaway

A start keeps climbing for three moves only if it is 3 more than a multiple of 4, because that is exactly when the number you get after halving is odd again.

  • Even starts lose on move one
  • Two of the three come free
  • Everything hinges on the parity of a₃
  • Name the odd start
  • Count the qualifying starts

More like this

Same archetype — closest grade level first.