AMC 10 · 2004 · #25

Grade 9 number-theorycounting

Archetype Pair-Sum Invariant └ Sub-archetype Universe Total Minus Known

place-valuedigit-countingcomplementary-countingleading-digit complementary-countingpattern-recognition ↑ Prerequisites: place-value

📏 Long solution 💡 4 insights

Problem

Two to the two thousand fourth has 604 digits and its first digit is 1. Count how many of the 2004 powers from the zeroth to the two thousand third have first digit 4.

Pick an answer.

(A)

194

(B)

195

(C)

196

(D)

197

(E)

198

How to solve

Strategy Change Focus / Count the Complement

"First digit is d" is really a statement about which slice of a power-of-ten band the number lands in, so rewrite it that way first. Then doubling moves a number through those slices in a rigid pattern: a power starting with 1 is followed by one starting with 2 or 3, then by one starting with 4 through 7. That pattern sorts all 2004 exponents into a few classes whose sizes are easy to count, and the class of first digit 4 is reached from the leftover class by one more doubling.

1STEP 1

Rewrite "first digit" as a band

A first digit is really a statement about a range, not about digits.

10^j ≤ N ＜ 10^j+1 and d · 10^j ≤ N ＜ (d+1) · 10^j ⇔ N has j+1 digits and leads with d

2STEP 2

Each band holds exactly one power starting with 1

Each range holds exactly one power starting with 1, and none is skipped.

2^k-1 ＜ 10^j ≤ 2^k ⟹ 10^j ≤ 2^k ＜ 2 · 10^j

3STEP 3

Count the powers starting with 1

The given fact makes that count 603.

5 · 10⁶⁰² ≤ 2²⁰⁰³ ＜ 10⁶⁰³ ⟹ #{k ≤ 2003 : 2^k starts with 1} = 603

4STEP 4

Follow the doubling chain

Doubling matches leading-1 powers one to one with two other classes.

1 ⟶ {2,3} ⟶ {4,5,6,7} ⟶ {8,9} or 1

5STEP 5

Check the shifts stay inside the set

Checking the shifted exponents confirms they all stay inside the set.

#{2,3} = #{4,5,6,7} = #{1} = 603

6STEP 6

Take the complement

The leftover class therefore has 195 members.

#{8,9} = 2004 - 3 · 603 = 195

7STEP 7

Shift once more to reach first digit 4

One more halving pairs that class with first digit 4, giving 195, choice (B).

2^k starts with 8 or 9 ⇔ 2^k-1 starts with 4 ⟹ #{4} = 195

Answer

195

First a size check. A power of 2 starts with 4 when its leading part lies in [4,5), which is a proportion log₁₀ 5/4 ≈ 0.0969 of a band, predicting about 0.0969 · 2004 ≈ 194.2 members. The answer 195 sits right there — but so do 194 and 196, which is exactly why the estimate cannot settle the problem and the exact band argument is needed. Second, an explicit test on a small stretch. The first digits of 2⁰ through 2²⁰ are 1, 2, 4, 8, 1, 3, 6, 1, 2, 5, 1, 2, 4, 8, 1, 3, 6, 1, 2, 5, 1. Among k = 0 to 19 there are exactly two leading 4s (at k = 2 and k = 12) and exactly two leading 8s or 9s (at k = 3 and k = 13), each leading 8 sitting one step after a leading 4 — the pairing used in the last step, verified by hand. The same list also shows leading 1s at k = 0, 4, 7, 10, 14, 17, 20, so the leading 1s really do arrive once per band, never twice and never skipped.

💡Key takeaway

A leading digit is just a range in disguise, and doubling moves that range in a fixed cycle — so you can count first digits of huge powers without ever writing one down.

Rewrite "first digit" as a band
Each band holds exactly one power starting with 1
Count the powers starting with 1
Follow the doubling chain
Check the shifts stay inside the set
Take the complement
Shift once more to reach first digit 4