2020 AMC 10A Problems/Problem 22
Contents
[hide]Problem
For how many positive integers is
not 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
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.