AMC 10 · 2004 · #24
Grade 8 arithmeticLet f be a function with the following properties:
(i) f(1)=1, and
(ii) f(2n)=n⋅f(n) for any positive integer n.
What is the value of f(2100)?
Pick an answer.
AMC 10 2004 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
Toolkit + CCSS Solution
Understand
Restated: 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.
Givens: f(1) = 1.; f(2n) = n \cdot f(n) for every positive integer n.
Unknowns: The value of f(2^{100}).
Understand
Restated: 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.
Givens: f(1) = 1.; f(2n) = n \cdot f(n) for every positive integer n.
Plan
Primary tool: #5 Look for a Pattern
Secondary: #9 Solve an Easier Related Problem
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.
Execute — Answer: D
4.OA.C.5 Step 1 Work out the small powers of 2
- Start from f(1) = 1 and climb using f(2n) = n \cdot f(n).
- Each time, n is the number you are doubling.
- f(2) uses n = 1, f(4) uses n = 2, f(8) uses n = 4, and f(16) uses n = 8.
- Then rewrite each answer as a power of 2 to make the pattern visible.
💡 Trying the first few powers of 2 turns an abstract rule into concrete numbers you can stare at.
8.EE.A.1 Step 2 See how the exponent grows
- The exponents so far are 0, 1, 3, 6 for f(2^{1}), f(2^{2}), f(2^{3}), f(2^{4}).
- Look at why: going from f(2^{k}) to f(2^{k+1}) uses n = 2^{k}, so you multiply by 2^{k}.
- Multiplying by 2^{k} adds k to the exponent.
- So the exponent of f(2^{k}) is the running total 0 + 1 + 2 + \cdots + (k-1).
- To reach f(2^{100}) the exponent is the sum of every whole number from 0 up to 99.
💡 Each doubling multiplies by the next power of 2, so the exponents just pile up one on top of another.
5.NBT.B.5 Step 3 Add 0 through 99 and read off the answer
- Sum the whole numbers from 0 to 99.
- Pair them from the ends: 0 + 99, 1 + 98, 2 + 97, and so on.
- There are 50 such pairs and each pair totals 99, so the sum is 50 \times 99 = 4950.
- Therefore f(2^{100}) = 2^{4950}, which is choice (D).
💡 Pairing the smallest with the largest makes every pair the same size, so one multiplication finishes the sum.
4.OA.C.5 Start from f(1) = 1 and climb using f(2n) = n \cdot f(n). Each time, n is the nu 8.EE.A.1 The exponents so far are 0, 1, 3, 6 for f(2^{1}), f(2^{2}), f(2^{3}), f(2^{4}). 5.NBT.B.5 Sum the whole numbers from 0 to 99. Pair them from the ends: 0 + 99, 1 + 98, 2 + Review
Reasonableness: 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.
Alternative: Instead of climbing up, unfold the rule straight down in one line: f(2^{100}) = 2^{99}\cdot f(2^{99}) = 2^{99}\cdot 2^{98}\cdot f(2^{98}) = \cdots = 2^{99}\cdot 2^{98}\cdots 2^{1}\cdot 2^{0}\cdot f(1). Multiplying powers of 2 adds their exponents, giving 2^{99+98+\cdots+0}=2^{4950}, the same answer.
CCSS standards used (min grade 8)
4.OA.C.5Generate a number or shape pattern following a given rule (Applying f(2n)=n\cdot f(n) to build f(2), f(4), f(8), f(16) and writing each as a power of 2.)8.EE.A.1Know and apply the properties of integer exponents (Recognizing that multiplying f(2^{k}) by 2^{k} adds k to the exponent, so the exponent of f(2^{100}) is 0+1+\cdots+99.)5.NBT.B.5Fluently multiply multi-digit whole numbers (Summing 0 through 99 by pairing into 50 pairs of 99 and computing 50\times 99 = 4950.)
⭐ 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.
⭐ 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.
More like this
Same archetype — closest grade level first.