AMC 10 · 2004 · #24

Grade 8 arithmetic

Archetype Arithmetic Expression Decomposition └ Sub-archetype Successive Multiplicative Steps

recursive-sequenceexponentstriangular-numbers pattern-recognitioneasier-related-problem ↑ Prerequisites: exponents

📏 Medium solution 💡 2 insights

Problem

A function f obeys two rules: f(1) = 1, and for every positive integer n, f(2n) = n times f(n). Using only these rules, find the value of f at 2 raised to the 100th power.

Pick an answer.

(A)

$\ 1$

(B)

$\ 2^{99}$

(C)

$\ 2^{100}$

(D)

$\ 2^{4950}$

(E)

$\ 2^{9999}$

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

How to solve

Strategy Look for a Pattern

The exponent 100 is impossible to attack directly, so first work out f on the small powers of 2 — f(2), f(4), f(8), f(16) — where the rule can be applied by hand. Writing each result as a power of 2 exposes a clean pattern in the exponents. Once the pattern is clear, the same rule shows exactly how the exponent grows at each doubling, turning the whole problem into a single sum of the numbers 0 through 99.

1STEP 1

Work out the small powers of 2

Start at f(1) = 1 and climb to f(2), f(4), f(8), f(16) in turn, writing each result as a power of 2.

f(2)=1 · f(1)=1=2⁰, f(4)=2 · f(2)=2=2¹, f(8)=4 · f(4)=8=2³, f(16)=8 · f(8)=64=2⁶

2STEP 2

See how the exponent grows

The exponents 0, 1, 3, 6 pile up because each f(2ᵏ) → f(2ᵏ⁺¹) multiplies by 2ᵏ, so f(2¹⁰⁰) has exponent 0 + 1 + … + 99.

f(2^k+1)=2^k · f(2^k) → exponent of f(2¹⁰⁰) = 0+1+2+…+99

3STEP 3

Add 0 through 99 and read off the answer

Pair the ends — 0 + 99, 1 + 98, … — 50 pairs of 99, so the sum is 4950 and f(2¹⁰⁰) = 2⁴⁹⁵⁰, choice (D).

0+1+…+99=(99 · 100)/2=50 × 99=4950 → f(2¹⁰⁰)=2⁴⁹⁵⁰

Answer

2⁴⁹⁵⁰

The exponents 0, 1, 3, 6 match the running sums 0, 0+1, 0+1+2, 0+1+2+3, so the running-total idea fits the hand-computed cases exactly. The final exponent 4950 also equals 99 times 100 divided by 2, the standard count for adding 0 through 99. The answer is a gigantic power of 2, which fits a rule that multiplies by ever-larger powers of 2 at every step, and it lands on one of the offered choices.

💡Key takeaway

When a rule is too big to plug into, try the first few cases, write them as powers, and let the pattern in the exponents do the heavy lifting.

Work out the small powers of 2
See how the exponent grows
Add 0 through 99 and read off the answer

Work out the small powers of 2

See how the exponent grows

Add 0 through 99 and read off the answer

More like this