2020 AMC 10A Problems/Problem 22
Contents
Problem
For how many positive integers isnot divisible by ? (Recall that is the greatest integer less than or equal to .)
Solution (Casework)
Expression:
Solution:
Let
Since , for any integer , the difference between the largest and smallest terms before the function is applied is less than or equal to , and thus the terms must have a range of or less after the function is applied.
This means that for every integer ,
if is an integer and , then the three terms in the expression above must be ,
if is an integer because , then will be an integer and will be greater than ; thus the three terms in the expression must be ,
if is an integer, then the three terms in the expression above must be ,
if is an integer, then the three terms in the expression above must be , and
if none of are integral, then the three terms in the expression above must be .
The last statement is true because in order for the terms to be different, there must be some integer in the interval or the interval . However, this means that multiplying the integer by should produce a new integer between and or and , exclusive, but because no such integers exist, the terms cannot be different, and thus, must be equal.
Note that does not work; to prove this, we just have to substitute for in the expression.
This gives us
which is divisible by 3.
Now, we test the five cases listed above (where )
Case 1: divides and
As mentioned above, the three terms in the expression are , so the sum is , which is divisible by . Therefore, the first case does not work.
Case 2: divides and
As mentioned above, in this case the terms must be , which means the sum is , so the expression is not divisible by . Therefore, this is case that works.
Case 3: divides
Because divides , the number of possibilities for is the same as the number of factors of .
= . So, the total number of factors of is .
However, we have to subtract , because the case does not work, as mentioned previously. This leaves cases.
Case 4: divides
Because divides , the number of possibilities for is the same as the number of factors of .
= . So, the total number of factors of is .
Again, we have to subtract , so this leaves cases. We have also overcounted the factor , as it has been counted as a factor of and as a separate case. , so there are actually valid cases.
Case 5: divides none of
Similar to Case 1, the value of the terms of the expression are . The sum is , which is divisible by 3, so this case does not work.
Now that we have counted all of the cases, we add them.
, so the answer is .
~dragonchomper, additional edits by emerald_block
Solution (Extremely Simple and a bit cheating)
You can find that you only need to count the number of factors of 1000 and 999. 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=.-happykeeper
Video Solution
~IceMatrix
See Also
2020 AMC 10A (Problems • Answer Key • Resources) | ||
Preceded by Problem 21 |
Followed by Problem 23 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | ||
All AMC 10 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.