AMC 10 · 2020 · #22

Grade 6 number-theory

Archetype Small-Domain Constrained Search

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

📏 Long solution 💡 3 insights

Problem

For how many positive integers $n \le 1000$ is $\left\lfloor \dfrac{998}{n} \right\rfloor+\left\lfloor \dfrac{999}{n} \right\rfloor+\left\lfloor \dfrac{1000}{n}\right \rfloor$ not divisible by $3$ ? (Recall that $\lfloor x \rfloor$ is the greatest integer less than or equal to $x$ .)

$\textbf{(A) } 22 \qquad\textbf{(B) } 23 \qquad\textbf{(C) } 24 \qquad\textbf{(D) } 25 \qquad\textbf{(E) } 26$

Pick an answer.

(A)

(B)

(C)

(D)

(E)

View mode:

Toolkit + CCSS Solution

Understand

Restated: For how many positive integers $n \le 1000$ is the sum $S(n) = \lfloor 998/n \rfloor + \lfloor 999/n \rfloor + \lfloor 1000/n \rfloor$ NOT a multiple of $3$? Here $\lfloor x \rfloor$ is the greatest integer $\le x$.

Givens: Three consecutive numerators $998, 999, 1000$ divided by the same $n$; $n$ ranges over positive integers $\le 1000$; $999 = 3^3 \cdot 37$ and $1000 = 2^3 \cdot 5^3$ (factorizations are useful); Answer choices: (A) $22$, (B) $23$, (C) $24$, (D) $25$, (E) $26$

Unknowns: Count of $n$ for which $S(n)$ is NOT divisible by $3$

Understand

Plan

Primary tool: #9 Solve an Easier Related Problem

Secondary: #5 Look for a Pattern, #16 Change Focus / Complement, #2 Make a Systematic List, #3 Eliminate Possibilities

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.

Execute — Answer: A

#9 Solve an Easier Related Problem 6.NS.B.2 Step 1

Try small values to build intuition.
For $n = 7$: $\lfloor 998/7 \rfloor = 142$, $\lfloor 999/7 \rfloor = 142$, $\lfloor 1000/7 \rfloor = 142$.
Sum $= 426 = 3 \cdot 142$, divisible by $3$.
For $n = 8$ (which divides $1000$): $\lfloor 998/8 \rfloor = 124$, $\lfloor 999/8 \rfloor = 124$, $\lfloor 1000/8 \rfloor = 125$.
Sum $= 373$, NOT divisible by $3$.
For $n = 9$ (which divides $999$): $\lfloor 998/9 \rfloor = 110$, $\lfloor 999/9 \rfloor = 111$, $\lfloor 1000/9 \rfloor = 111$.
Sum $= 332$, NOT divisible by $3$.
Pattern emerging: a "jump" in the floor occurs exactly when a multiple of $n$ sits at $999$ or $1000$.

$$n=7: 142+142+142 = 426 \;(\div 3 \;\checkmark);\;\; n=8: 124+124+125 = 373\;(\not\div 3);\;\; n=9: 110+111+111 = 332\;(\not\div 3)$$

💡 Hand-compute a few cases — see that floors agree unless $n$ "hits" $999$ or $1000$ on the nose.

#5 Look for a Pattern 6.NS.B.2 Step 2

Find the general rule.
Write $999 = nq + r$ with $0 \le r < n$, so $\lfloor 999/n \rfloor = q$.
Then $998 = nq + (r-1)$ and $1000 = nq + (r+1)$.
Three sub-cases by where $r$ sits: (i) $1 \le r \le n-2$: all three remainders are in $[0, n-1]$, so all three floors equal $q$, sum $= 3q \equiv 0 \pmod 3$.
(ii) $r = 0$ (i.e.
$n \mid 999$): then $998$ has remainder $n-1 \Rightarrow \lfloor 998/n \rfloor = q-1$; $1000$ has remainder $1 \Rightarrow \lfloor 1000/n \rfloor = q$.
Sum $= (q-1) + q + q = 3q - 1 \equiv 2 \pmod 3$.
(iii) $r = n-1$ (i.e.
$n \mid 1000$): then $998$ has remainder $n-2 \Rightarrow \lfloor 998/n \rfloor = q$; $1000$ has remainder $0 \Rightarrow \lfloor 1000/n \rfloor = q + 1$.
Sum $= q + q + (q+1) = 3q + 1 \equiv 1 \pmod 3$.
So $S(n)$ is non-divisible by $3$ iff $n \mid 999$ or $n \mid 1000$.

$$S(n) \not\equiv 0 \pmod 3 \iff n \mid 999 \text{ or } n \mid 1000$$

💡 The three floors split into a clean pattern indexed by the remainder of $999 \bmod n$.

#3 Eliminate Possibilities 3.OA.B.5 Step 3

But check the corner case $n = 1$: then $r = 0$ AND $r = n - 1 = 0$ simultaneously — case (ii) and (iii) collide.
Direct: $\lfloor 998 \rfloor + \lfloor 999 \rfloor + \lfloor 1000 \rfloor = 998+999+1000 = 2997 = 3 \cdot 999$, divisible by $3$.
So $n = 1$ does NOT count, even though it divides both $999$ and $1000$.

$$n = 1: S(1) = 2997 = 3 \cdot 999 \;\Rightarrow\; \text{divisible by } 3$$

💡 $n=1$ is the only common divisor — and it sneaks past the rule.

#2 Make a Systematic List 6.NS.B.4 Step 4

Count divisors of $999$ and $1000$.
Factor: $999 = 27 \cdot 37 = 3^3 \cdot 37^1$.
Number of divisors $= (3+1)(1+1) = 8$.
The divisors are $1, 3, 9, 27, 37, 111, 333, 999$.
Factor: $1000 = 8 \cdot 125 = 2^3 \cdot 5^3$.
Number of divisors $= (3+1)(3+1) = 16$.
The divisors are $1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000$.

$$d(999) = 8, \quad d(1000) = 16$$

💡 Standard divisor formula on the prime factorizations.

#16 Change Focus / Complement 6.NS.B.4 Step 5

Combine via inclusion-exclusion.
The common divisors of $999$ and $1000$ are divisors of $\gcd(999, 1000) = 1$, i.e.
just $\{1\}$.
So $|\{n : n \mid 999\} \cup \{n : n \mid 1000\}| = 8 + 16 - 1 = 23$.
Subtract the corner case $n = 1$, which is in this union but does NOT contribute: final count $= 23 - 1 = 22$.

$$\text{answer} = 8 + 16 - 1 - 1 = 22 \Rightarrow \textbf{(A)}$$

💡 Inclusion-exclusion on the two divisor lists; then peel off the broken $n=1$.

[1] #9 6.NS.B.2 Try small values to build intuition. For $n = 7$: $\lfloor 998/7 \rfloor = 142$,

[2] #5 6.NS.B.2 Find the general rule. Write $999 = nq + r$ with $0 \le r < n$, so $\lfloor 999/

[3] #3 3.OA.B.5 But check the corner case $n = 1$: then $r = 0$ AND $r = n - 1 = 0$ simultaneous

[4] #2 6.NS.B.4 Count divisors of $999$ and $1000$. Factor: $999 = 27 \cdot 37 = 3^3 \cdot 37^1$

[5] #16 6.NS.B.4 Combine via inclusion-exclusion. The common divisors of $999$ and $1000$ are div

Review

Reasonableness: Every $n$ in the answer is $\le 1000$ (automatic, since divisors of $999$ or $1000$ are $\le 1000$). Spot-check $n = 8$ (divides $1000$, not $999$): sum $= 373$, $373 = 3 \cdot 124 + 1$, not divisible. Spot-check $n = 37$ (divides $999$, not $1000$): $\lfloor 998/37 \rfloor = 26, \lfloor 999/37 \rfloor = 27, \lfloor 1000/37 \rfloor = 27$, sum $= 80 = 3 \cdot 27 - 1$, not divisible. Spot-check $n = 2$ (divides $1000$, not $999$): floors are $499, 499, 500$, sum $= 1498 = 3 \cdot 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.

Alternative: Tool #2 (Systematic List) alone: simply enumerate every $n$ for which $S(n)$ is not divisible by $3$ in a computer-style table. Going $n = 2, 3, 4, \ldots$ and checking the three floors finds the same $22$ values. The advantage of the divisor-list method is that we don't have to check $999$ values of $n$ one by one.

CCSS standards used (min grade 6)

3.OA.B.5 Apply properties of operations as strategies to multiply and divide (Directly checking the $n = 1$ corner case via $998 + 999 + 1000 = 2997 = 3 \cdot 999$.)
6.NS.B.2 Fluently divide multi-digit numbers using the standard algorithm (Computing quotients and remainders of $998, 999, 1000$ by $n$ to identify when the three floors differ.)
6.NS.B.4 Find greatest common factor and least common multiple of two numbers (Factoring $999 = 3^3 \cdot 37$ and $1000 = 2^3 \cdot 5^3$, counting divisors via the exponent formula, and using $\gcd(999, 1000) = 1$ for inclusion-exclusion.)

⭐ 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$.

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: A

Review

CCSS standards used (min grade 6)

More like this