AMC 10 · 2005 · #22

Grade 7 number-theory
Archetype Small-Domain Constrained Search └ Sub-archetype Factor / Divisibility Constraint
factorialprime-numberstriangular-numbersdivisibility-rules complementary-countingpattern-recognition ↑ Prerequisites: factorialprime-numberstriangular-numbers
📏 Long solution 💡 3 insights
Problem
For each positive integer n from 1 to 24, compare the factorial n! = 1 · 2 · 3 … n with the running sum 1 + 2 + … + n. How many of these values of n make n! evenly divisible by that sum?

Pick an answer.

(A)
8
(B)
12
(C)
16
(D)
17
(E)
21

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

How to solve
Strategy Change Focus / Count the Complement

Checking all 24 values one by one is slow, so Tool #4 (Introduce a Variable) first replaces the sum with the formula (n(n+1))/2 and simplifies the quotient into one clean fraction — that turns a divisibility puzzle about n! into a question about a single factor n+1. Tool #5 (Look for a Pattern) then tests what kind of n+1 breaks the divisibility, and the pattern is sharp: it fails exactly when n+1 is an odd prime and works every other time. Because the failures are the rare cases, Tool #16 (Count the Complement) is the efficient finish — count the odd primes that fail and subtract from 24 instead of hunting for the many that succeed.

1STEP 1

Replace the sum with a formula

The divisor 1 + 2 + … + n is an arithmetic sum equal to (n(n+1))/2, so we ask instead when n! divided by that value is a whole number.

1 + 2 + … + n = (n(n+1))/2
2STEP 2

Simplify the quotient

Dividing by that fraction flips it, and since n! = n · (n-1)! the shared n cancels, leaving (2 (n-1)!)/(n+1) — everything now hangs on n+1.

n!/(n(n+1)/2) = 2 n!/(n(n+1)) = (2 (n-1)!)/(n+1)
3STEP 3

See when it fails: n+1 an odd prime

If n+1 is an odd prime p, it divides neither 2 nor (n-1)! = 1 · 2 … (p-2), whose factors are all smaller than p — so those n fail.

p prime, p ＞ 2 → p ∤ 2 and p ∤ (p-2)! → p ∤ 2 (n-1)!
4STEP 4

See when it works: everything else

Any other n+1 divides in: its factors already sit inside (n-1)! (for 9, the 3 and the 6), and n+1 = 2 and 4 check out by hand.

n+1 = ab, 1 ＜ a ＜ b ≤ n-1 → (n+1) ∣ (n-1)! ∣ 2 (n-1)!
5STEP 5

Count the complement

Only odd-prime n+1 fails; from 2 to 25 those are 3, 5, 7, 11, 13, 17, 19, 23, eight in all, so 24 - 8 = 16 values work.

24 - #{3,5,7,11,13,17,19,23} = 24 - 8 = 16 → (C)
Answer
16
The eight failing values of n are 2, 4, 6, 10, 12, 16, 18, 22 — precisely the n where n+1 is an odd prime — and checking any of them by hand agrees: for n = 4, the sum is 10 but 4! = 24 is not a multiple of 10. The successes include easy sanity checks like n = 3 (sum 6, and 3! = 6) and n = 5 (sum 15, and 5! = 120 = 15 · 8). Since failures are the exception, an answer near the top of the range is expected, and 16 out of 24 fits; the far-smaller choices 8 and 12 would need far more failures than the handful of odd primes allow.
💡Key takeaway

Rewrite 1 + 2 + … + n as (n(n+1))/2, simplify, and the divisibility fails only when n+1 is an odd prime — so count those 8 primes and subtract from 24 to get 16.

  • Replace the sum with a formula
  • Simplify the quotient
  • See when it fails: n+1 an odd prime
  • See when it works: everything else
  • Count the complement

More like this

Same archetype — closest grade level first.