AMC 10 · 2020 · #22

Grade 6 number-theory

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

floor-functiondivisibility-rulesdivisor-countmodular-arithmeticpattern-recognition complementary-countingpattern-recognitioncasework ↑ Prerequisites: floor-functiondivisor-count

📏 Long solution 💡 3 insights

Problem

For how many positive integers n ≤ 1000 is the sum S(n) = ⌊

\frac{998}{n}

⌋ + ⌊

\frac{999}{n}

⌋ + ⌊

\frac{1000}{n}

⌋ NOT a multiple of 3? Here ⌊ x ⌋ is the greatest integer ≤ x.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

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

How to solve

Strategy Solve an Easier Related Problem

Tool #9 (Easier Problem): try small n (1, 2, 3, 6, 7, 8, ...) by hand to see when the three floors agree vs. differ. Tool #5 (Pattern): the three floors agree unless a multiple of n lands at 999 or 1000 — a clean trigger condition. Tool #16 (Complement): instead of counting non-multiples of 3 directly, identify exactly which n break the all-equal pattern (only divisors of 999 or 1000 can). Tool #2 (Systematic List): list divisors of 999 and 1000. Tool #3 (Eliminate Possibilities): catch the n=1 corner case that satisfies the rule but is actually divisible.

1STEP 1

Hand-test small n: n = 7 gives three equal floors, sum divisible by 3; but n = 8 makes them jump to 124, 124, 125, sum 373 — not divisible.

n=7: 142+142+142 = 426 (÷ 3 ✓); n=8: 124+124+125 = 373 ( not ÷ 3); n=9: 110+111+111 = 332 ( not ÷ 3)

2STEP 2

Writing 999 = nq + r, the floors all equal q unless r = 0 or n-1 — so the sum avoids a multiple of 3 exactly when n divides 999 or 1000.

S(n) ≢ 0 (mod 3) ⇔ n ∣ 999 or n ∣ 1000

3STEP 3

Corner case n = 1: S(1) = 998 + 999 + 1000 = 2997 = 3 · 999, divisible by 3 — so n = 1 fails despite dividing both.

n = 1: S(1) = 2997 = 3 · 999 → divisible by 3

4STEP 4

Factor 999 = 3³ · 37, giving (3+1)(1+1) = 8 divisors; factor 1000 = 2³ · 5³, giving (3+1)(3+1) = 16 divisors.

d(999) = 8, d(1000) = 16

5STEP 5

By inclusion-exclusion the union has 8 + 16 - 1 = 23 divisors (they share only 1); removing the broken n = 1 leaves 22 values — answer (A).

answer = 8 + 16 - 1 - 1 = 22 → (A)

Answer

Every n in the answer is ≤ 1000 (automatic, since divisors of 999 or 1000 are ≤ 1000). Spot-check n = 8 (divides 1000, not 999): sum = 373, 373 = 3 · 124 + 1, not divisible. Spot-check n = 37 (divides 999, not 1000): ⌊

\frac{998}{37}

⌋ = 26, ⌊

\frac{999}{37}

⌋ = 27, ⌊

\frac{1000}{37}

⌋ = 27, sum = 80 = 3 · 27 - 1, not divisible. Spot-check n = 2 (divides 1000, not 999): floors are 499, 499, 500, sum = 1498 = 3 · 499 + 1, not divisible. The count 22 matches the 7 + 15 = 22 obtained by listing divisors of 999 (excluding 1) plus divisors of 1000 (excluding 1), with no other overlap. Choice (B) 23 is the natural trap if one forgets the n=1 exclusion.

💡Key takeaway

This AMC 10 problem only needs Grade 6 divisibility and divisor counting you already know — the three floors only "break" their pattern when n divides 999 or 1000, and counting those divisors (8 + 16 - 1 overlap) and subtracting the trick n=1 gives 22.

More like this