2020 AMC 10 A

Complete problem set with solutions and individual problem pages

Problem 22 Hard

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

  • A.

    22

  • B.

    23

  • C.

    24

  • D.

    25

  • E.

    26

Answer:A

Solution 1 (Casework):

Expression: \left[\frac{998}{n}\right\rfloor+\left\lfloor\frac{999}{n}\right\rfloor+\left\lfloor\frac{1000}{n}\right\rfloor

Solution: Let a=\left[\frac{998}{n}\right\rfloor Since \frac{1000}{n}-\frac{998}{n}=\frac{2}{n}, for any integer n \geq 2, the difference between the largest and smallest terms before the \lfloor x\rfloor function is applied is less than or equal to 1 , and thus the terms must have a range of 1 or less after the function is applied.

This means that for every integer n \geq 2, 998 - if \bar{n} is an integer and n \neq 2, then the three terms in the expression above must be (a, a, a),- if \frac{998}{n} is an integer because n=2, then \frac{1000}{n} will be an integer and will be 1 greater than \frac{998}{n}; thus the three terms in the expression must be (a, a, a+1), 999 - if n is an integer, then the three terms in the expression above must be (a, a+1, a+1), \frac{1000}{n} - if n is an integer, then the three terms in the expression above must be (a, a, a+1), and \left\{\frac{998}{n}, \frac{999}{n}, \frac{1000}{n}\right\} - if none of \left\{\frac{n}{n}, \frac{n}{\text { are integral, then the three terms in the }}\right. expression above must be (a, a, a).

The last statement is true because in order for the terms to be different, there must be some integer in the interval \left(\frac{998}{n}, \frac{999}{n}\right) or the interval \left(\frac{999}{n}, \frac{1000}{n}\right).

However, this means that multiplying the integer interval by n should produce a new integer between 998 and 999 or 999 and 1000 , exclusive, but because no such integers exist, the terms cannot be different, and thus, must be equal. - Note that n=1 does not work; to prove this, we just have to substitute 1 for n in the expression.

This gives us \left\lfloor\frac{998}{1}\right\rfloor+\left\lfloor\frac{999}{1}\right\rfloor+\left\lfloor\frac{1000}{1}\right\rfloor=998+999+1000=2997=999 \cdot 3 which is divisible by 3 . Now, we test the five cases listed above (where n \geq 2 )

Case 1: n divides 998 and n \neq 2 As mentioned above, the three terms in the expression are (a, a, a), so the sum is 3 a, which is divisible by 3 . Therefore, the first case does not work (0 cases).

Case 2: n divides 998 and n=2 As mentioned above, in this case the terms must be (a, a, a+1), which means the sum is 3 a+1, so the expression is not divisible by 3 . Therefore, this is 1 case that works.

Case 3: n divides 999 Because n divides 999 , the number of possibilities for n is the same as the number of factors of 999 999=3^{3} \cdot 37^{1}. So, the total number of factors of 999 is 4 \cdot 2=8. However, we have to subtract 1 , because the case n=1 does not work, as mentioned previously. This leaves 8-1=7 cases.

Case 4: n divides 1000 Because n divides 1000 , the number of possibilities for n is the same as the number of factors of 1000 . 1000=5^{3} \cdot 2^{3}. So, the total number of factors of 1000 is 4 \cdot 4=16. Again, we have to subtract 1 , so this leaves 16-1=15 cases. We have also overcounted the factor 2 , as it has been counted as a factor of 1000 and as a separate case (Case 2). 15-1=14, so there are actually 14 valid cases.

Case 5: n divides none of \{998,999,1000\} Similar to Case 1, the value of the terms of the expression are (a, a, a). The sum is 3 a, which is divisible by 3 , so this case does not work (0 cases). Now that we have counted all of the cases, we add them. 0+1+7+14+0=22, so the answer is (\mathbf{A}) 22

Solution 2 (Solution 1 but simpler): * Note that this solution does not count a majority of cases that are important to consider in similar problems, though they are not needed for this problem, and therefore it may not work with other, similar problems. Notice that you only need to count the number of factors of 1000 and 999 , excluding 1. 1000 has 16 factors, and 999 has 8 . Adding them gives you 24 , but you need to subtract 2 since 1 does not work. Therefore, the answer is 24-2= (A) 22 .

Related Problems
Problem 20 2020 AMC 10 A
Problem 21 2020 AMC 10 A
Problem 23 2020 AMC 10 A
Problem 24 2020 AMC 10 A
Think Academy Powered by ChatGPT