Difference between revisions of "2020 AMC 10A Problems/Problem 22"
(→Solution (Casework)) |
(→Solution 2) |
||
(88 intermediate revisions by 26 users not shown) | |||
Line 5: | Line 5: | ||
<math>\textbf{(A) } 22 \qquad\textbf{(B) } 23 \qquad\textbf{(C) } 24 \qquad\textbf{(D) } 25 \qquad\textbf{(E) } 26</math> | <math>\textbf{(A) } 22 \qquad\textbf{(B) } 23 \qquad\textbf{(C) } 24 \qquad\textbf{(D) } 25 \qquad\textbf{(E) } 26</math> | ||
+ | == Solution 1 == | ||
+ | Clearly, <math>n=1</math> fails. Except for the special case of <math>n=1</math>, | ||
+ | <cmath>\left\lfloor \frac{1000}{n} \right\rfloor - \left\lfloor \frac{998}{n} \right\rfloor</cmath> | ||
+ | equals either <math>0</math> or <math>1</math>. If it equals <math>0</math>, this implies that <math>\left\lfloor \frac{998}{n} \right\rfloor = \left\lfloor \frac{999}{n} \right\rfloor = \left\lfloor \frac{1000}{n} \right\rfloor</math>, so their sum is clearly a multiple of <math>3</math>, so this will always fail. If it equals <math>1</math>, the sum of the three floor terms is <math>3 \left\lfloor \frac{999}{n} \right\rfloor \pm 1</math>, so it is never a multiple of <math>3</math>. Thus, we are looking for all <math>n \neq 1</math> such that | ||
+ | <cmath>\left\lfloor \frac{1000}{n} \right\rfloor - \left\lfloor \frac{998}{n} \right\rfloor = 1.</cmath> | ||
+ | This implies that either | ||
+ | <cmath>\left\lfloor \frac{998}{n} \right\rfloor + 1 = \left\lfloor \frac{999}{n} \right\rfloor,</cmath> | ||
+ | or | ||
+ | <cmath>\left\lfloor \frac{999}{n} \right\rfloor + 1 = \left\lfloor \frac{1000}{n} \right\rfloor.</cmath> | ||
− | == | + | Let's analyze the first equation of these two. This equation is equivalent to the statement that there is a positive integer <math>a</math> such that |
+ | <cmath>\frac{998}{n} < a \leq \frac{999}{n} \implies 998 < an \leq 999 \implies an = 999 \implies a = \frac{999}{n} \implies n | 999.*</cmath> | ||
+ | Analogously, the second equation implies that | ||
+ | <cmath>n | 1000.</cmath> | ||
+ | So our only <math>n</math> that satisfy this condition are <math>n \neq 1</math> that divide <math>999</math> or <math>1000</math>. Using the method to find the number of divisors of a number, we see that <math>999</math> has <math>8</math> divisors and <math>1000</math> has <math>16</math> divisors. Their only common factor is <math>1</math>, so there are <math>8+16-1 = 23</math> positive integers that divide either <math>999</math> or <math>1000</math>. Since the integer <math>1</math> is a special case and does not count, we must subtract this from our <math>23</math>, so our final answer is <math>23-1 = \boxed{\textbf{(A) } 22}.</math> | ||
− | < | + | *While this observation may seem strange, it is actually "trivial by intuition" to go straight from <math>\left\lfloor \frac{998}{n} \right\rfloor + 1 = \left\lfloor \frac{999}{n} \right\rfloor</math> to <math>n | 999</math>. In fact, "trivial by intuition" is basically a good summary of the solution to this entire problem. |
− | |||
− | + | ~ihatemath123 | |
− | + | == Solution 2 == | |
− | + | Counting down <math>n</math> from <math>1000</math>, <math>999</math>, <math>998</math>... we notice that <math>\left\lfloor \dfrac{998}{n} \right\rfloor+\left\lfloor \dfrac{999}{n} \right\rfloor+\left\lfloor \dfrac{1000}{n}\right \rfloor</math> is only not divisible by <math>3</math> when n is a divisor of ''only'' <math>1000</math> or <math>999 (1000, 999, 500, 333</math>...). Notice how the factors of <math>998: 1, 2, 499</math>, and <math>998</math>, do not work. | |
− | <math> | + | The prime factorization of <math>999</math> is <math>3^3\cdot37</math>, so <math>4\cdot2=8</math> factors in total. |
− | <math> | + | The prime factorization of <math>1000</math> is <math>2^3\cdot5^3</math>, so <math>4\cdot4=16</math> factors in total. |
− | <math> | + | However, <math>1</math> obviously does not work, so we have to subtract <math>2</math> (<math>1</math> is counted twice) from the total. <math>8 + 16 - 2</math> = <math>\boxed{\textbf{(A)}22}</math>. |
− | + | ~BLOATED_BAGEL | |
− | + | ~Typo fixed by evanhliu2009 | |
+ | == Solution 3 == | ||
+ | First, we notice the following lemma: | ||
− | + | <math>\textbf{Lemma}</math>: For <math>N, n \in \mathbb{N}</math>, <math> \left\lfloor \frac{N}{n} \right\rfloor = \left\lfloor \frac{N-1}{n} \right\rfloor + 1 </math> if <math>n \mid N</math>; and <math>\left\lfloor \frac{N}{n} \right\rfloor = \left\lfloor \frac{N-1}{n} \right\rfloor</math> if <math>n \nmid N.</math> | |
− | |||
− | <math>\left\lfloor \ | ||
− | |||
+ | <math>\textbf{Proof}</math>: Let <math>A = kn + r</math>, with <math>0 \leq r < n</math>. If <math>n \mid N</math>, then <math>r = 0</math>. Hence <math>\left\lfloor \frac{N}{n} \right\rfloor = k</math>, <math>\left\lfloor \frac{N-1}{n} \right\rfloor = \left\lfloor \frac{(k-1)n+n-1}{n} \right\rfloor = k-1 + \left\lfloor \frac{n-1}{n} \right\rfloor = k-1</math>, and <math>\left\lfloor \frac{N}{n} \right\rfloor = \left\lfloor \frac{N-1}{n} \right\rfloor + 1.</math> | ||
− | + | If <math>n \nmid N</math>, then <math>1 \leq r < n</math>. Hence <math>\left\lfloor \frac{N}{n} \right\rfloor = k</math>, <math>\left\lfloor \frac{N-1}{n} \right\rfloor = k + \left\lfloor \frac{r-1}{n} \right\rfloor = k</math>, and <math>\left\lfloor \frac{N}{n} \right\rfloor = \left\lfloor \frac{N-1}{n} \right\rfloor.</math> | |
+ | From the lemma and the given equation, we have four possible cases: | ||
+ | <cmath>\left\lfloor \frac{998}{n} \right\rfloor + 1 = \left\lfloor \frac{999}{n} \right\rfloor = \left\lfloor \frac{1000}{n} \right\rfloor - 1 \qquad (1)</cmath> | ||
+ | <cmath>\left\lfloor \frac{998}{n} \right\rfloor + 1 = \left\lfloor \frac{999}{n} \right\rfloor + 1 = \left\lfloor \frac{1000}{n} \right\rfloor \qquad (2)</cmath> | ||
+ | <cmath>\left\lfloor \frac{998}{n} \right\rfloor + 1 = \left\lfloor \frac{999}{n} \right\rfloor = \left\lfloor \frac{1000}{n} \right\rfloor \qquad (3)</cmath> | ||
+ | <cmath>\left\lfloor \frac{998}{n} \right\rfloor = \left\lfloor \frac{999}{n} \right\rfloor = \left\lfloor \frac{1000}{n} \right\rfloor \qquad (4)</cmath> | ||
− | < | + | Note that cases (2) and (3) are the cases in which the term, <math>\left\lfloor \frac{998}{n} \right\rfloor + \left\lfloor \frac{999}{n} \right\rfloor + \left\lfloor \frac{1000}{n} \right\rfloor,</math> is not divisible by <math>3</math>. So we only need to count the number of <math>n</math>'s for which cases (2) and (3) stand. |
− | + | Case (2): By the lemma, we have <math>n \mid 1000</math> and <math>n \nmid 999.</math> Hence <math>n</math> can be any factor of <math>1000</math> except for <math>n = 1</math>. Since <math>1000 = 2^3 * 5^3,</math> there are <math>(3+1)(3+1) - 1 = 15</math> possible values of <math>n</math> for this case. | |
+ | Case (3): By the lemma, we have <math>n \mid 999</math> and <math>n \nmid 998.</math> Hence <math>n</math> can be any factor of <math>999</math> except for <math>n = 1</math>. Since <math>999 = 3^3 * 37^1,</math> there are <math>(3+1)(1+1) - 1 = 7</math> possible values of <math>n</math> for this case. | ||
− | + | So in total, we have total of <math>15+7=\boxed{\textbf{(A)}22}</math> possible <math>n</math>'s. | |
− | + | ~mathboywannabe | |
− | |||
− | |||
− | + | == Solution 4 (Casework)== | |
− | |||
− | + | Note that <math>\left\lfloor \frac{998}{n} \right\rfloor + \left\lfloor \frac{999}{n} \right\rfloor + \left\lfloor \frac{1000}{n} \right\rfloor</math> is a multiple of <math>3</math> if <math>\left\lfloor \frac{998}{n} \right\rfloor + \left\lfloor \frac{999}{n} \right\rfloor + \left\lfloor \frac{1000}{n} \right\rfloor</math> lies between two consecutive multiples of <math>n</math>. | |
− | < | + | <math>\textbf{Explanation:}</math> |
− | |||
− | |||
− | |||
− | + | Let's assume that the above expression does indeed lie betweent two consecutive multiples of <math>n</math>. This implies that <math>n</math> does not divide either <math>998, 999</math> or <math>1000</math>, meaning that when divided by <math>n</math>, none of the quotients are whole. In turn, this also means that they will all have the same whole number part. | |
− | <math> | ||
− | |||
− | + | If <math>\frac{998}{n}, \frac{999}{n},</math> and <math>\frac{1000}{n}</math> were to have a different whole number part, then <math>n</math> would have to lie within <math>998</math> and <math>1000</math>. If this is confusing, think of why <math>\frac{6}{5}, \frac{7}{5}</math> and <math>\frac{8}{5}</math> have the same whole number part (<math>1</math> in this case). Here, <math>n=5</math>. What happens to the whole number part when <math>n=7</math>? | |
− | |||
+ | Since <math>\frac{998}{n}, \frac{999}{n},</math> and <math>\frac{1000}{n}</math> have identical whole number parts, their floors are identical, since the floor of a number is equal to its whole number part, discarding its fractional component. | ||
− | |||
− | + | Let <math>k</math> be the number we get when we floor <math>\frac{998}{n}, \frac{999}{n},</math> or <math>\frac{1000}{n}</math> if the three of those numbers lie between two consecutive multiples of <math>n</math>. Adding them up, we get <math>3k</math> (due to their floors being the same), which is a mulutiple of <math>3</math>. So no matter what, we cannot have <math>\frac{998}{n}, \frac{999}{n},</math> and <math>\frac{1000}{n}</math> lie between two consecutive multiples of <math>n</math>. | |
− | |||
− | ~ | + | |
+ | What does this mean? It means that there must be some multiple of <math>n</math> within this expression (with some restrictions, as we'll see), in order to prevent the violation of the main restriction. We can proceed with casework now. | ||
+ | |||
+ | |||
+ | <math>\textbf{Case 1}</math> | ||
+ | |||
+ | |||
+ | Let's assume that the multiple of <math>n</math> is located at <math>\frac{998}{n}</math>. Luckily, the only prime factors of <math>998</math> are <math>2</math> and <math>499</math>. | ||
+ | |||
+ | |||
+ | We can observe that <math>499</math> doesn't work, since <math>\frac{998}{499}</math> and <math>\frac{1000}{499}</math> will both round down to <math>2</math> when divided by it. However, <math>2</math> does work, since it divides both <math>998</math> and <math>1000</math>. The floor of <math>\frac{999}{2}</math> is <math>499</math>, , meaning that when we evaluate the given expression for <math>n=2</math>, we will get <math>2\cdot{499}+500</math> which isn't a multiple of <math>3</math>. | ||
+ | |||
+ | |||
+ | This case works because we have a multiple of <math>n</math> at the end of the expression, as well as the beginning, so the whole number parts of <math>998, 999</math> and <math>1000</math> when divided by <math>n</math> are not all the same, due to <math>n</math> dividing two of these numbers. | ||
+ | |||
+ | The restriction of <math>n</math> dividing more than one number within the expression is only valid when we're testing the first number in the given expression (otherwise, the other floors wouldn't round down to the same value as the first). | ||
+ | |||
+ | Case <math>1</math> is complete, and we've found that only <math>2</math> works. | ||
+ | |||
+ | |||
+ | <math>\textbf{Case 2}</math> | ||
+ | |||
+ | Now, let's assume that the multiple of <math>n</math> is located at <math>\frac{999}{n}</math>. In this case, if <math>n</math> divides <math>999</math>, it doesn't divide <math>998</math> (since two multiples of a number greater than <math>1</math> are never consecutive), nor does it divide <math>1000</math>, for the same reason. | ||
+ | |||
+ | |||
+ | The prime factorization of <math>999</math> is <math>3^3\cdot37</math>, and thus has <math>(3+1)(1+1)=8</math> divisors. | ||
+ | |||
+ | |||
+ | When testing a few values of <math>n</math> initially, we observed that <math>n=1</math> causes the expression to be divisible by <math>3</math>. Subtracting <math>1</math>, we see that there are <math>7</math> values of <math>n</math> that work for this case. | ||
+ | |||
+ | |||
+ | <math>\textbf{Case 3}</math> | ||
+ | |||
+ | Finally, let's assume that the multiple of <math>n</math> is located at <math>\frac{1000}{n}.</math> | ||
+ | |||
+ | |||
+ | Our goal is to have the other multiple of <math>n</math> below whatever <math>\frac{998}{n}</math> is, so we won't have identical floors throughout the expression. | ||
+ | |||
+ | |||
+ | Once again, any factor of <math>1000</math>, except for <math>2</math> is relatively prime to both <math>998</math> and <math>999</math>, so when we floor those two numbers, we get an integer that isn't <math>500</math>. | ||
+ | |||
+ | |||
+ | <math>1000</math> factors as <math>2^3\cdot{5^3}</math>, meaning that it has <math>(3+1)(3+1)=16</math> divisors. <math>1</math> and <math>2</math> either don't work or have already been counted, so there are <math>14</math> valid values of <math>n</math> for this case. | ||
+ | |||
+ | |||
+ | <math>\textbf{Ending}</math> | ||
+ | |||
+ | |||
+ | Adding these three cases, we get <math>1+7+14= \boxed{\textbf{A) }22} </math> values of <math>n</math>. | ||
+ | |||
+ | -Benedict T (countmath1) | ||
+ | |||
+ | ==Video Solutions== | ||
+ | ===Video Solution 1 (Simple)=== | ||
+ | Education, The Study of Everything | ||
+ | |||
+ | https://youtu.be/LWAYKQQX6KI | ||
+ | |||
+ | |||
+ | ===Video Solution 2=== | ||
+ | https://www.youtube.com/watch?v=_Ej9nnHS07s | ||
+ | |||
+ | ~Snore | ||
+ | |||
+ | ===Video Solution 3=== | ||
+ | https://www.youtube.com/watch?v=G5UVS5aM-CY&list=PLLCzevlMcsWNcTZEaxHe8VaccrhubDOlQ&index=4 ~ MathEx | ||
+ | |||
+ | ===Video Solution 4 (Richard Rusczyk)=== | ||
+ | https://artofproblemsolving.com/videos/amc/2020amc10a/517 | ||
==See Also== | ==See Also== |
Latest revision as of 22:13, 29 September 2023
Contents
Problem
For how many positive integers is
not divisible by
? (Recall that
is the greatest integer less than or equal to
.)
Solution 1
Clearly, fails. Except for the special case of
,
equals either
or
. If it equals
, this implies that
, so their sum is clearly a multiple of
, so this will always fail. If it equals
, the sum of the three floor terms is
, so it is never a multiple of
. Thus, we are looking for all
such that
This implies that either
or
Let's analyze the first equation of these two. This equation is equivalent to the statement that there is a positive integer such that
Analogously, the second equation implies that
So our only
that satisfy this condition are
that divide
or
. Using the method to find the number of divisors of a number, we see that
has
divisors and
has
divisors. Their only common factor is
, so there are
positive integers that divide either
or
. Since the integer
is a special case and does not count, we must subtract this from our
, so our final answer is
*While this observation may seem strange, it is actually "trivial by intuition" to go straight fromto
. In fact, "trivial by intuition" is basically a good summary of the solution to this entire problem.
~ihatemath123
Solution 2
Counting down from
,
,
... we notice that
is only not divisible by
when n is a divisor of only
or
...). Notice how the factors of
, and
, do not work.
The prime factorization of is
, so
factors in total.
The prime factorization of is
, so
factors in total.
However, obviously does not work, so we have to subtract
(
is counted twice) from the total.
=
.
~BLOATED_BAGEL
~Typo fixed by evanhliu2009
Solution 3
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
'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
Solution 4 (Casework)
Note that is a multiple of
if
lies between two consecutive multiples of
.
Let's assume that the above expression does indeed lie betweent two consecutive multiples of . This implies that
does not divide either
or
, meaning that when divided by
, none of the quotients are whole. In turn, this also means that they will all have the same whole number part.
If and
were to have a different whole number part, then
would have to lie within
and
. If this is confusing, think of why
and
have the same whole number part (
in this case). Here,
. What happens to the whole number part when
?
Since and
have identical whole number parts, their floors are identical, since the floor of a number is equal to its whole number part, discarding its fractional component.
Let be the number we get when we floor
or
if the three of those numbers lie between two consecutive multiples of
. Adding them up, we get
(due to their floors being the same), which is a mulutiple of
. So no matter what, we cannot have
and
lie between two consecutive multiples of
.
What does this mean? It means that there must be some multiple of within this expression (with some restrictions, as we'll see), in order to prevent the violation of the main restriction. We can proceed with casework now.
Let's assume that the multiple of is located at
. Luckily, the only prime factors of
are
and
.
We can observe that doesn't work, since
and
will both round down to
when divided by it. However,
does work, since it divides both
and
. The floor of
is
, , meaning that when we evaluate the given expression for
, we will get
which isn't a multiple of
.
This case works because we have a multiple of at the end of the expression, as well as the beginning, so the whole number parts of
and
when divided by
are not all the same, due to
dividing two of these numbers.
The restriction of dividing more than one number within the expression is only valid when we're testing the first number in the given expression (otherwise, the other floors wouldn't round down to the same value as the first).
Case is complete, and we've found that only
works.
Now, let's assume that the multiple of is located at
. In this case, if
divides
, it doesn't divide
(since two multiples of a number greater than
are never consecutive), nor does it divide
, for the same reason.
The prime factorization of is
, and thus has
divisors.
When testing a few values of initially, we observed that
causes the expression to be divisible by
. Subtracting
, we see that there are
values of
that work for this case.
Finally, let's assume that the multiple of is located at
Our goal is to have the other multiple of below whatever
is, so we won't have identical floors throughout the expression.
Once again, any factor of , except for
is relatively prime to both
and
, so when we floor those two numbers, we get an integer that isn't
.
factors as
, meaning that it has
divisors.
and
either don't work or have already been counted, so there are
valid values of
for this case.
Adding these three cases, we get values of
.
-Benedict T (countmath1)
Video Solutions
Video Solution 1 (Simple)
Education, The Study of Everything
Video Solution 2
https://www.youtube.com/watch?v=_Ej9nnHS07s
~Snore
Video Solution 3
https://www.youtube.com/watch?v=G5UVS5aM-CY&list=PLLCzevlMcsWNcTZEaxHe8VaccrhubDOlQ&index=4 ~ MathEx
Video Solution 4 (Richard Rusczyk)
https://artofproblemsolving.com/videos/amc/2020amc10a/517
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.