2004 AMC 10A Problem 24

P21-25~3 minPrint

Functions Sequences & Series Compute small cases, spot the pattern, generalize Collapse a sum or product by cancellation

Let $f$ be a function with the following properties:

(i) $f(1) = 1$ , and

(ii) $f(2n) = n \cdot f(n)$ for any positive integer $n$ .

What is the value of $f(2^{100})$ ?

Show solution without answering

Key insight

Climb the powers of 2 using the rule. Reaching 2 to the 100th multiplies factors 2 to the 0, 1, up to 99, so the exponent is 4950.

Solution

Start with small powers of $2$ to see what the rule does.

Rule (ii) with $n = 1$ : $f(2) = 1 \cdot f(1) = 1$ .
With $n = 2$ : $f(4) = 2 \cdot f(2) = 2$ .
With $n = 4$ : $f(8) = 4 \cdot f(4) = 4 \cdot 2 = 8$ .
With $n = 8$ : $f(16) = 8 \cdot f(8) = 8 \cdot 8 = 64$ .

Write these as powers of $2$ :

input	$2^1$	$2^2$	$2^3$	$2^4$
$f$	$2^0$	$2^1$	$2^3$	$2^6$

5. Why the exponents $0, 1, 3, 6$ ? Each step uses $n = 2^{k-1}$ , so it multiplies by $2^{k-1}$ :
$f(2^k) = 2^{k-1} \cdot f(2^{k-1}).$
Multiplying powers of $2$ adds their exponents. So the exponent of $f(2^k)$ is $0 + 1 + 2 + \cdots + (k-1)$ . For $k = 4$ that is $0 + 1 + 2 + 3 = 6$ , which matches.
6. For $k = 100$ , the exponent is
$0 + 1 + 2 + \cdots + 99 = \frac{99 \times 100}{2} = 4950.$

So $f(2^{100}) = 2^{4950}$ .

The answer is $\boxed{\textbf{(D)}\ 2^{4950}}$ .

Why this works

A rule that links $f(2n)$ to $f(n)$ lets you climb the powers of $2$ one step at a time, multiplying by one new factor at each step. Working out the first few values shows the pattern, and a table of exponents makes it plain that you are adding $0 + 1 + 2 + \cdots$ . Be careful where the sum ends: to reach $2^{100}$ the last factor is $2^{99}$ , not $2^{100}$ .

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Put $n = 2^{k-1}$ in rule (ii). Since $2n = 2^k$ , the rule reads
$f(2^k) = 2^{k-1} \cdot f(2^{k-1}) \qquad (k \ge 1).$

Chain these from $k = 100$ down to $k = 1$ :
$f(2^{100}) = 2^{99} f(2^{99}) = 2^{99} \cdot 2^{98} f(2^{98}) = \cdots = 2^{99} \cdot 2^{98} \cdots 2^{1} \cdot 2^{0} \cdot f(1).$
With $f(1) = 1$ , the product is a single power of $2$ whose exponent is
$99 + 98 + \cdots + 1 + 0 = \frac{99 \cdot 100}{2} = 4950.$

The answer is $\boxed{\textbf{(D)}\ 2^{4950}}$ .

Review in the AoPS books

Introduction to Algebra, Chapter 16: Functions
Introduction to Algebra, Chapter 21: Sequences & Series (§21.1, §21.2, §21.3, §21.4)
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.1)
Introduction to Algebra, Chapter 17: Graphing Functions (§17.2)