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 1 (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 (0 cases).
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 1 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
7 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 (Case 2).
, so there are actually 14 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 (0 cases).
Now that we have counted all of the cases, we add them.
, so the answer is
.
~dragonchomper, additional edits by emerald_block
Solution 2 (Solution 1 but simpler)
Notice that you only need to count the number of factors of and
, excluding
.
has
factors, and
has
.
Adding them gives you
, but you need to subtract
since
does not work.
Therefore, the answer is .
-happykeeper, additional edits by dragonchomper, even more edits by ericshi1685
Solution 3 - Solution 1 but much simpler
NOTE: For this problem, whenever I say , I will be referring to all the factors of the number except for
.
Now, quickly observe that if divides
, then
and
will also round down to
, giving us a sum of
, which does not work for the question. However, if
divides
, we see that
and
. This gives us a sum of
, which is clearly not divisible by
. Using the same logic, we can deduce that
too works (for our problem). Thus, we need the factors of
and
and we don't have to eliminate any because the
. But we have to be careful! See that when
, then our problem doesn't get fulfilled. The only
that satisfies that is
. So, we have:
;
.
Adding them up gives a total of
workable
's.
Solution 4
Writing out , we see that the answer cannot be more than the number of divisors of
since all
satisfying the problem requirements are among the divisors of
. There are
total divisors, and we subtract
from the start because we count
, which never works, thrice.
From the divisors of , note that
and
don't work. 2 to subtract.
Also note that we count
twice, in
and
, so we have to subtract another from the running total of
.
Already, we are at divisors so we conclude that the answer is
.
Solution 4
First, we notice the following lemma:
: For
,
if
; and
if
: Let
, with
. If
, then
. Hence
,
, and
If , then
. Hence
,
, and
From the lemma and the given equation, we have four possible cases:
Note that cases (2) and (3) are the cases in which the term, is not divisible by
. So we only need to count the number of n's for which cases (2) and (3) stand.
Case (2): By the lemma, we have and
Hence
can be any factor of
except for
. Since
there are
possible values of
for this case.
Case (3): By the lemma, we have and
Hence
can be any factor of
except for
. Since
there are
possible values of
for this case.
So in total, we have total of possible
's.
~mathboywannabe
Video Solution
https://www.youtube.com/watch?v=_Ej9nnHS07s
~Snore
Video Solution
https://www.youtube.com/watch?v=G5UVS5aM-CY&list=PLLCzevlMcsWNcTZEaxHe8VaccrhubDOlQ&index=4 ~ MathEx
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.