Skip to main content

2020 AMC 10A Problem 22

Problem 22 of 25HarderAlgebraNumber Theory

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

Answer choices

Show solution

Solution

Write 1000=qn+r1000=qn+r, where 0r<n0\le r<n. Then 1000n=q\left\lfloor\dfrac{1000}{n}\right\rfloor=q. The other two floors are usually also qq, except that subtracting 11 or 22 from 10001000 crosses a multiple of nn when rr is small. For n>1n>1, the sum is not divisible by 33 exactly when r=0r=0 or r=1r=1. The case r=0r=0 gives divisors of 10001000, excluding 11, for 1515 values. The case r=1r=1 gives divisors of 999999, excluding 11, for (3+1)(1+1)1=7(3+1)(1+1)-1=7 values. The total is 2222. Thus, A is the correct answer.

More practice

Concepts: floor and ceiling functions · divisibility · factor counting

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.