2020 AMC 10A Problem 22

P21-25~6 minPrint

Number Properties Divisibility & Factors Split into exhaustive cases and handle each Set up the equation/formula and compute; no special trick needed

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

Show solution without answering

Key insight

The three floors are equal, so their sum is a multiple of 3, unless n divides 999 or 1000. Count those divisors, leaving out n = 1.

Solution

First see how the three floors compare. Try an example: $n = 7$ . Then $\frac{998}{7} \approx 142.6$ , $\frac{999}{7} \approx 142.7$ , $\frac{1000}{7} \approx 142.9$ . All three floors are $142$ , and the sum $3 \times 142$ is a multiple of $3$ .

When does the floor go up? As the top goes $998 \to 999 \to 1000$ , the floor of (top $\div n$ ) goes up by $1$ only when the top hits a multiple of $n$ . So the three floors are all equal unless $n$ divides $999$ or $n$ divides $1000$ .
Case: $n$ divides neither. All three floors equal some $q$ . The sum is $3q$ , a multiple of $3$ . Not counted.
Case: $n$ divides $999$ but not $1000$ . Example $n = 37$ : floors $26, 27, 27$ . The floor steps up at $999$ , so the floors are $q - 1, q, q$ and the sum is $3q - 1$ . Not a multiple of $3$ . Counted.
Case: $n$ divides $1000$ but not $999$ . Example $n = 8$ : floors $124, 124, 125$ . The sum is $3q - 2$ . Not a multiple of $3$ . Counted.
Case: $n$ divides both. Two numbers in a row share no common factor except $1$ , so $n = 1$ . The sum is $998 + 999 + 1000 = 2997 = 3 \times 999$ , a multiple of $3$ . Not counted.
Count the divisors. $999 = 3^3 \times 37$ has $4 \times 2 = 8$ divisors. $1000 = 2^3 \times 5^3$ has $4 \times 4 = 16$ divisors. Leave $n = 1$ out of each list: $7 + 15 = 22$ . All of these are at most $1000$ , as the problem requires.

The answer is $\boxed{\textbf{(A)}\ 22}$ .

Why this works

Floors of nearby fractions with the same bottom are almost always equal, and three equal numbers always add to a multiple of $3$ . So the only interesting $n$ are the ones where the floor "steps up", and that happens exactly at divisors. Then it is a divisor count, with one special number ( $n = 1$ ) to watch.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

As $m$ increases by $1$ , $\lfloor m/n \rfloor$ increases only when $m$ becomes a multiple of $n$ . So the three floors for $m = 998, 999, 1000$ are all equal unless $n$ divides $999$ or $1000$ .

Case 1: $n$ divides neither. All three floors equal some $q$ , the sum is $3q$ , divisible by $3$ . Not counted.

Case 2: $n \mid 999$ but $n \nmid 1000$ . Then $\lfloor 999/n \rfloor = \lfloor 1000/n \rfloor = q$ and $\lfloor 998/n \rfloor = q - 1$ . Sum $3q - 1$ : not divisible by $3$ . Counted.

Case 3: $n \mid 1000$ but $n \nmid 999$ . Then $\lfloor 1000/n \rfloor = q$ and the other two are $q - 1$ . Sum $3q - 2$ : counted.

Case 4: $n$ divides both $999$ and $1000$ . Consecutive integers are coprime, so only $n = 1$ ; the sum $998 + 999 + 1000 = 2997 = 3 \cdot 999$ is divisible by $3$ . Not counted.

Now count. $999 = 3^3 \cdot 37$ has $4 \cdot 2 = 8$ divisors; $1000 = 2^3 \cdot 5^3$ has $4 \cdot 4 = 16$ . Removing $n = 1$ from each list leaves $7 + 15 = 22$ values, all at most $1000$ .

The answer is $\boxed{\textbf{(A)}\ 22}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 1: Integers: The Basics
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.2)
Introduction to Algebra, Chapter 20: Special Functions (§20.3)
Introduction to Number Theory, Chapter 5: Divisor Problems (§5.2, §5.3)