AMC 10 · 2021 · #25

Grade 11 number-theory

Archetype Small-Domain Constrained Search └ Sub-archetype Factor / Divisibility Constraint

divisor-countprime-factorizationoptimizationexponents identify-subproblemsextreme-principle ↑ Prerequisites: divisor-count

📏 Long solution 💡 3 insights

Problem

For each positive integer, consider its number of divisors divided by its cube root. Exactly one positive integer makes this strictly larger than it is for every other. Find the sum of the digits of that integer.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

How to solve

Strategy Identify Subproblems

Searching all positive integers is hopeless head-on, so the whole solution rests on Tool #7 (Identify Subproblems): once f is rewritten as a product with one factor per prime, and the exponents of different primes can be chosen independently, the single global maximization splits into a separate tiny maximization for each prime. Tool #4 (Introduce a Variable) sets that up by naming the exponents a₁,a₂,… in the prime factorization. Tool #15 (Organize Information in More Ways) is the rewriting move itself — regrouping d(n)/∛(n) from "count over root" into "product of per-prime pieces". Tool #14 (Extreme Principle) converts "where is the peak?" into a comparison between consecutive exponents, which cubes into pure whole-number arithmetic. Tool #6 (Guess and Check) then runs that cheap test on p=2,3,5,7, and Tool #3 (Eliminate Possibilities) kills every prime from 11 upward in one stroke.

1STEP 1

Count the divisors

Write the divisor count from the exponents.

n=p₁^a₁p₂^a₂… p_k^a_k ⟹ d(n)=(a₁+1)(a₂+1)…(a_k+1)

2STEP 2

Split into one factor per prime

It splits prime by prime.

f(n)=d(n)/∛(n)=a₁+1{p₁^a₁/3}·a₂+1{p₂^a₂/3}…a_k+1{p_k^a_k/3}=Π_i=1^kg_p_i(a_i), g_p(a)=a+1{p^a/3}

3STEP 3

Maximize each prime alone

Maximize each factor independently.

f(n)=Π_p prime g_p(a_p) with each a_p free, g_p(0)=1

4STEP 4

Test whether one more pays

See whether one more copy pays.

(g_p(a+1))/g_p(a)=a+2{(a+1) p¹/3} ＞ 1 ⇔ (a+2)³ ＞ p(a+1)³

5STEP 5

Run it on the small primes

Find the best exponent for each small prime.

p=2: a=3; p=3: a=2; p=5: a=1; p=7: a=1

6STEP 6

Discard big primes and multiply

Multiplying and adding digits gives 9.

N=2³·3²·5¹·7¹=2520, 2+5+2+0=9 → (E)

Answer

Test N=2520 against its closest rivals. Here d(2520)=4·3·2·2=48 and ∛(2520)≈13.61, so f(2520)≈3.53. Doubling to 5040=2⁴·3²·5·7 gives d=60 and ∛(5040)≈17.14, so f≈3.50 — smaller, matching the finding that the exponent of 2 should stop at 3. Halving to 1260=2²·3²·5·7 gives d=36 and ∛(1260)≈10.80, so f≈3.33 — also smaller. Attaching the next prime, 27720=2520·11, gives d=96 and ∛(27720)≈30.26, so f≈3.17, clearly worse. A second, independent check comes from the answer choices themselves: 3² divides N, so 9 divides N, so the digit sum of N must be a multiple of 9; among 5,6,7,8,9 only 9 qualifies. The number 2520 is also recognizable as lcm(1,2,…,10), exactly the kind of divisor-rich value that should win a contest of this shape.

💡Key takeaway

Break the function into one piece per prime, ask each prime "is one more copy worth it?", and the answers stop at 2³·3²·5·7=2520, whose digits add to 9.

Count divisors from the exponents
Split f into one factor per prime
Maximize each prime's factor alone
Test whether one more copy pays
Run the test on the small primes
Discard the large primes and multiply