Problem:
For how many positive integers nβ€1000 is
βn998ββ+βn999ββ+βn1000ββ
not divisible by 3? (Recall that βxβ is the greatest integer less than or equal to x.)
Answer Choices:
A. 22
B. 23
C. 24
D. 25
E. 26
Solution:
Clearly, n=1 fails. Except for the special case of n=1,
βn1000ββββn998ββ
equals either 0or1. If it equals 0, this implies that βn998ββ=βn999ββ=βn1000ββ, 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[n999β]Β±1, so it is never a multiple of 3. Thus, we are looking for all nξ =1 such that
βn1000ββββn998ββ=1
This implies that either
βn998ββ+1=βn999ββ
or
βn999ββ+1=βn1000ββ
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
n998β<aβ€n999ββΉ998<anβ€999βΉan=999βΉa=n999ββΉnβ£β£β£β£β£β999.
Analogously, the second equation implies that
nβ£1000
So our only n that satisfy this condition are nξ =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=(A) 22β.
OR
Counting down n from 1000,999,998β¦ we notice that βn998ββ+βn999ββ+βn1000ββ is only not divisible by 3 when n is a divisor of only 1000 or 999(1000,999,500,333β¦). Notice how the factors of 998:1,2,499, and 998 , do not work.
The prime factorization of 999 is 33β
37, so 4β
2=8 factors in total. The prime factorization of 1000 is 23β
53, so 4β
4=16 factors in total. However, 1 obviously does not work, so we have to subtract 2 (1 is counted twice) from the total.
8+16β2=(A) 22β
The problems on this page are the property of the MAA's American Mathematics Competitions