AMC10 2020 10A, Problem 22

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

Solution: Clearly, $n=1$ fails. Except for the special case of $n=1$, \[\left\lfloor \frac{1000}{n} \right\rfloor - \left\lfloor \frac{998}{n} \right\rfloor\] equals either $0$ or $1$. If it equals $0$, this implies that $\left\lfloor \frac{998}{n} \right\rfloor = \left\lfloor \frac{999}{n} \right\rfloor = \left\lfloor \frac{1000}{n} \right\rfloor$, so their sum is clearly a multiple of $3$, so this will always fail. If it equals $1$, the sum of the three floor terms is $3 \left\lfloor \frac{999}{n} \right\rfloor \pm 1$, so it is never a multiple of $3$. Thus, we are looking for all $n \neq 1$ such that \[\left\lfloor \frac{1000}{n} \right\rfloor - \left\lfloor \frac{998}{n} \right\rfloor = 1.\] This implies that either \[\left\lfloor \frac{998}{n} \right\rfloor + 1 = \left\lfloor \frac{999}{n} \right\rfloor,\] or \[\left\lfloor \frac{999}{n} \right\rfloor + 1 = \left\lfloor \frac{1000}{n} \right\rfloor.\] Let's analyze the first equation of these two. This equation is equivalent to the statement that there is a positive integer $a$ such that \[\frac{998}{n} < a \leq \frac{999}{n} \implies 998 < an \leq 999 \implies an = 999 \implies a = \frac{999}{n} \implies n | 999.*\] Analogously, the second equation implies that \[n | 1000.\] So our only $n$ that satisfy this condition are $n \neq 1$ that divide $999$ or $1000$. Using the method to find the number of divisors of a number, we see that $999$ has $8$ divisors and $1000$ has $16$ divisors. Their only common factor is $1$, so there are $8+16-1 = 23$ positive integers that divide either $999$ or $1000$. Since the integer $1$ is a special case and does not count, we must subtract this from our $23$, so our final answer is $23-1 = \fbox{22}.$ *While this observation may seem strange, it is actually "trivial by intuition" to go straight from $\left\lfloor \frac{998}{n} \right\rfloor + 1 = \left\lfloor \frac{999}{n} \right\rfloor$ to $n | 999$. In fact, "trivial by intuition" is basically a good summary of the solution to this entire problem.

Answer: 22