AMC 10 · 2004 · #17

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}$

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

Climbing from the known value gives exponents 0, 1, 3, 6 for the first few powers.

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

Each doubling multiplies by a power of two, so the exponent is a running total of the step numbers.

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

Pairing from the ends sums zero through ninety-nine to 4950, giving 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