Difference between revisions of "2020 AMC 10A Problems/Problem 22"
Amitav2005 (talk | contribs) (→Solution 3 - Solution 1 but much simpler) |
m |
||
Line 102: | Line 102: | ||
<math>1000=2^3\cdot 5^3 \implies (3+1)(3+1)-1 \text{*factors*} \implies 15</math>. | <math>1000=2^3\cdot 5^3 \implies (3+1)(3+1)-1 \text{*factors*} \implies 15</math>. | ||
Adding them up gives a total of <math>7+15=\boxed{\textbf{(A)}22}</math> workable <math>n</math>'s. | Adding them up gives a total of <math>7+15=\boxed{\textbf{(A)}22}</math> workable <math>n</math>'s. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
== Solution 4 == | == Solution 4 == |
Revision as of 15:55, 7 September 2020
Contents
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)
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 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.