2020 AMC 10A Problems/Problem 22
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, then the three terms in the expression above must be ,
if is an integer, then the three terms in the expression above must be ,
if is an integer and (since if , will be an integer, and it will be greater than ), 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 original integer cannot exist, and thus, the terms 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 four cases listed above.
Case 1: divides
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
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 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 .
Again, we have to subtract , so this leaves cases.
Case 4: divides none of
As in 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
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.