AMC 10 · 2022 · #23
Grade 11 number-theoryPick an answer.
Computing 22 harmonic fractions and reducing each one is brutal by hand, so I reorganize the information instead. First I write the whole sum over the single denominator L_n; then k_n ＜ L_n says exactly that the numerator and L_n share a prime factor. That converts one hard fraction question into a divisibility question I can attack one prime at a time. For a fixed prime p, almost every term of the numerator is a multiple of p and dies modulo p, leaving a sum of at most p-1 modular inverses. That short sum is easy to evaluate, and one clean pattern in it (M=p-1 always gives zero) does most of the work. Finally I list the primes up to 22, read off which n each one catches, and take the union.
Put the sum over one denominator
Put the whole sum over the lcm.
Once the sum sits over one denominator, "did the fraction shrink?" is just "does some prime divide the top?".
7.NS.A.1Organize Information In More WaysFix one prime
Fix one prime and its exponent.
Dividing L_n by j just subtracts j's supply of p from the e copies that L_n holds.
8.EE.A.1Introduce A VariableMost terms vanish
Most terms are divisible by that prime.
A term only matters mod p if j used up every copy of p that L_n had.
9.A-SSE.A.2Solve An Easier Related ProblemA short inverse sum survives
What survives is a short sum of inverses.
A monstrous numerator shrinks to a harmonic sum with fewer than p terms, read inside the clock arithmetic of p.
9.A-SSE.A.2Introduce A VariableTwo decisive facts
Two facts decide most cases.
Inverting 1 through p-1 only shuffles that list, so their sum is the same old (p(p-1))/2, which p divides.
Taking reciprocals only shuffles the list of nonzero remainders, so their total is unchanged.
▸ Why?
Each remainder has exactly one reciprocal partner and each is somebody's partner, so the list maps onto itself.
▸ Why?
Pairing the list's two ends gives a constant total, so the sum is fixed no matter how it is shuffled.
Sweep the primes
Sweep every prime up to twenty-two.
Only 3 and 5 get a wide enough window below 22 to reach the sum that vanishes.
6.NS.B.4Make A Systematic ListUnion and count
The union has size 8.
Overlapping catches still count once, so the answer is the size of the union, not the total of the two lists.
6.NS.B.4Make A Systematic ListPut the whole sum over one denominator, then ask each prime by itself whether it divides the top — a monstrous fraction turns into a few tiny sums on a clock.
- Put the whole sum over L_n
- Fix one prime and its exponent
- Most terms vanish modulo p
- What survives is a short inverse sum
- Two facts that decide most cases
- Sweep the primes up to 22
- Union the lists and count