Difference between revisions of "2020 AMC 10A Problems/Problem 22"

(Solution 4)
m (Solution 4 (If you don't understand the intuition in previous solutions): Removed the loooong title. Everything else is good!)
(47 intermediate revisions by 18 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>
  
== Solution 1 (Casework) ==
+
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>
  
<b>Expression:</b>
+
*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.
<cmath>\left\lfloor \dfrac{998}{n} \right\rfloor+\left\lfloor \dfrac{999}{n} \right\rfloor+\left\lfloor \dfrac{1000}{n}\right \rfloor</cmath>
 
  
<b>Solution:</b>
+
~ihatemath123
  
Let <math>a = \left\lfloor \frac{998}n \right\rfloor</math>
+
== Solution 2 ==
  
Since <math>\frac{1000}n - \frac{998}n = \frac{2}n</math>, for any integer <math>n \geq 2</math>, the difference between the largest and smallest terms before the <math>\lfloor x \rfloor</math> function is applied is less than or equal to <math>1</math>, and thus the terms must have a range of <math>1</math> or less after the function is applied.
+
Writing out <math>n = 1, 2, 3, 4 ... 11</math>, we see that the answer cannot be more than the number of divisors of <math>998, 999, 1000</math> since all <math>n</math> satisfying the problem requirements are among the divisors of <math>998, 999, 1000</math>. There are <math>28</math> total divisors, and we subtract <math>3</math> from the start because we count <math>1</math>, which never works, thrice.  
  
This means that for every integer <math>n \geq 2</math>,
+
From the divisors of <math>998</math>, note that <math>499</math> and <math>998</math> don't work. <math>2</math> to subtract.
 +
Also note that we count <math>2</math> twice, in <math>998</math> and <math>1000</math>, so we have to subtract another from the running total of <math>25</math>.
  
<math>\bullet</math> if <math>\frac{998}n</math> is an integer and <math>n \neq 2</math>, then the three terms in the expression above must be <math>(a, a, a)</math>,
+
Already, we are at <math>22</math> divisors so we conclude that the answer is <math>\boxed{\textbf{(A)}22}</math>.
  
<math>\bullet</math> if <math>\frac{998}n</math> is an integer because <math>n = 2</math>, then <math>\frac{1000}n</math> will be an integer and will be <math>1</math> greater than <math>\frac{998}n</math>; thus the three terms in the expression must be <math>(a, a, a + 1)</math>,
+
== Solution 3 ==
 +
First, we notice the following lemma:
  
<math>\bullet</math> if <math>\frac{999}n</math> is an integer, then the three terms in the expression above must be <math>(a, a + 1, a + 1)</math>,
+
<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>\bullet</math> if <math>\frac{1000}n</math> is an integer, then the three terms in the expression above must be <math>(a, a, a + 1)</math>, and
+
<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>
  
<math>\bullet</math> if none of <math>\left\{\frac{998}n, \frac{999}n, \frac{1000}n\right\}</math> are integral, then the three terms in the expression above must be <math>(a, a, a)</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>
  
The last statement is true because in order for the terms to be different, there must be some integer in the interval <math>\left(\frac{998}n, \frac{999}n\right)</math> or the interval <math>\left(\frac{999}n, \frac{1000}n\right)</math>. However, this means that multiplying the integer by <math>n</math> should produce a new integer between <math>998</math> and <math>999</math> or <math>999</math> and <math>1000</math>, exclusive, but because no such integers exist, the terms cannot be different, and thus, must be equal.
+
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.
  
<math>\bullet</math> Note that <math>n = 1</math> does not work; to prove this, we just have to substitute <math>1</math> for <math>n</math> in the expression.
+
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.
This gives us
 
<math>\left\lfloor \dfrac{998}{1} \right\rfloor+\left\lfloor \dfrac{999}{1} \right\rfloor+\left\lfloor \dfrac{1000}{1}\right \rfloor = 998 + 999 + 1000 = 2997 = 999 \cdot 3</math> which is divisible by 3.
 
  
 +
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.
  
Now, we test the five cases listed above (where <math>n \geq 2</math>)
+
So in total, we have total of <math>15+7=\boxed{\textbf{(A)}22}</math> possible <math>n</math>'s.
  
 +
~mathboywannabe
  
<b>Case 1:</b> <math>n</math> divides <math>998</math> and <math>n \neq 2</math>
+
== Solution 4 ==
 +
 
 +
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>
  
As mentioned above, the three terms in the expression are <math>(a, a, a)</math>, so the sum is <math>3a</math>, which is divisible by <math>3</math>.
 
Therefore, the first case does not work (<b>0</b> cases).
 
  
 +
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.
  
<b>Case 2:</b> <math>n</math> divides <math>998</math> and <math>n = 2</math>
 
  
As mentioned above, in this case the terms must be <math>(a, a, a + 1)</math>, which means the sum is <math>3a + 1</math>, so the expression is not divisible by <math>3</math>. Therefore, this is <b>1</b> case that works.
+
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>?
  
  
<b>Case 3:</b> <math>n</math> divides <math>999</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.
  
Because <math>n</math> divides <math>999</math>, the number of possibilities for <math>n</math> is the same as the number of factors of <math>999</math>.
 
  
<math>999</math> = <math>3^3 \cdot 37^1</math>.
+
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>.  
So, the total number of factors of <math>999</math> is <math>4 \cdot 2 = 8</math>.
 
  
However, we have to subtract <math>1</math>, because the case <math>n = 1</math> does not work, as mentioned previously. This leaves <math>8 - 1 =</math> <b>7</b> cases.
 
  
 +
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.
  
<b>Case 4:</b> <math>n</math> divides <math>1000</math>
 
  
Because <math>n</math> divides <math>1000</math>, the number of possibilities for <math>n</math> is the same as the number of factors of <math>1000</math>.
+
<math>\textbf{Case 1}</math>
  
<math>1000</math> = <math>5^3 \cdot 2^3</math>.
 
So, the total number of factors of <math>1000</math> is <math>4 \cdot 4 = 16</math>.
 
  
Again, we have to subtract <math>1</math>, so this leaves <math>16 - 1 = 15</math> cases.
+
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 have also overcounted the factor <math>2</math>, as it has been counted as a factor of <math>1000</math> and as a separate case (Case 2).
 
<math>15 - 1 = 14</math>, so there are actually <b>14</b> valid cases.
 
  
  
<b>Case 5:</b> <math>n</math> divides none of <math>\{998, 999, 1000\}</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>.
  
Similar to Case 1, the value of the terms of the expression are <math>(a, a, a)</math>. The sum is <math>3a</math>, which is divisible by 3, so this case does not work (<b>0</b> cases).
 
  
 +
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.
  
Now that we have counted all of the cases, we add them.
+
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).  
  
<math>0 + 1 + 7 + 14 + 0 = 22</math>, so the answer is <math>\boxed{\textbf{(A)}22}</math>.
+
Case <math>1</math> is complete, and we've found that only <math>2</math> works.  
  
~dragonchomper, additional edits by emerald_block
 
  
== Solution 2 (Solution 1 but simpler) ==
+
<math>\textbf{Case 2}</math>
<math>*</math> 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.
 
  
 +
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.
  
Notice that you only need to count the number of factors of 1000 and 999, excluding 1.
 
1000 has 16 factors, and 999 has 8.
 
Adding them gives you 24, but you need to subtract 2 since 1 does not work.
 
  
Therefore, the answer is 24 - 2 = <math>\boxed{\textbf{(A)}22}</math>.
+
The prime factorization of <math>999</math> is <math>3^3\cdot37</math>, and thus has <math>(3+1)(1+1)=8</math> divisors.  
  
-happykeeper, additional edits by dragonchomper
 
== Solution 3 - Solution 1 but much simpler ==
 
NOTE: For this problem, whenever I say <math>\text{*factors*}</math>, I will be referring to all the factors of the number except for <math>1</math>.
 
  
Now, quickly observe that if <math>n>2</math> divides <math>998</math>, then <math>\left\lfloor {\frac{999}{n}} \right\rfloor</math> and <math>\left\lfloor {\frac{1000}{n}} \right\rfloor</math> will also round down to <math>\frac{998}{n}</math>, giving us a sum of <math>3 \cdot \frac{998}{n}</math>, which does not work for the question. However, if <math>n>2</math> divides <math>999</math>, we see that <math>\left\lfloor {\frac{998}{n}} \right\rfloor = \frac{999}{n}-1</math> and <math>\left\lfloor {\frac{1000}{n}} \right\rfloor=\left\lfloor {\frac{999}{n}} \right\rfloor</math>. This gives us a sum of <math>3 \cdot \left\lfloor {\frac{999}{n}} \right\rfloor - 1</math>, which is clearly not divisible by <math>3</math>. Using the same logic, we can deduce that <math>(n>2)|1000</math> too works (for our problem). Thus, we need the factors of <math>999</math> and <math>1000</math> and we don't have to eliminate any because the <math>\text{gcf} (999,1000)=1</math>. But we have to be careful! See that when <math>n|998,999,1000</math>, then our problem doesn't get fulfilled. The only <math>n</math> that satisfies that is <math>n=1</math>. So, we have:
+
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>999=3^3\cdot 37 \implies (3+1)(1+1)-1 \text{*factors*} \implies 7</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.
 
  
== Solution 4 ==
 
First, we notice the following theorem:
 
  
If <math>n \mid N</math> where <math>N, n \in \mathbb{N}</math>, then <math>\left\lfloor \frac{N-1}{n} \right\rfloor + 1 = \left\lfloor \frac{N}{n} \right\rfloor</math>. And if <math>n \nmid N</math>, then <math>\left\lfloor \frac{N-1}{n} \right\rfloor = \left\lfloor \frac{N}{n} \right\rfloor</math>
+
<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
  
Proof: Let <math>A = kn + r</math>, 0
 
  
==Video Solution==
+
===Video Solution 2===
 
https://www.youtube.com/watch?v=_Ej9nnHS07s
 
https://www.youtube.com/watch?v=_Ej9nnHS07s
  
 
~Snore
 
~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==

Revision as of 14:31, 2 July 2022

Problem

For how many positive integers $n \le 1000$ is\[\left\lfloor \dfrac{998}{n} \right\rfloor+\left\lfloor \dfrac{999}{n} \right\rfloor+\left\lfloor \dfrac{1000}{n}\right \rfloor\]not divisible by $3$? (Recall that $\lfloor x \rfloor$ is the greatest integer less than or equal to $x$.)

$\textbf{(A) } 22 \qquad\textbf{(B) } 23 \qquad\textbf{(C) } 24 \qquad\textbf{(D) } 25 \qquad\textbf{(E) } 26$

Solution 1

Clearly, $n=1$ fails. Except for the special case of $n=1$, \[\left\lfloor \frac{1000}{n} \right\rfloor - \left\lfloor \frac{998}{n} \right\rfloor\] equals either $0$ or $1$. If it equals $0$, this implies that $\left\lfloor \frac{998}{n} \right\rfloor = \left\lfloor \frac{999}{n} \right\rfloor = \left\lfloor \frac{1000}{n} \right\rfloor$, so their sum is clearly a multiple of $3$, so this will always fail. If it equals $1$, the sum of the three floor terms is $3 \left\lfloor \frac{999}{n} \right\rfloor \pm 1$, so it is never a multiple of $3$. Thus, we are looking for all $n \neq 1$ such that \[\left\lfloor \frac{1000}{n} \right\rfloor - \left\lfloor \frac{998}{n} \right\rfloor = 1.\] This implies that either \[\left\lfloor \frac{998}{n} \right\rfloor + 1 = \left\lfloor \frac{999}{n} \right\rfloor,\] or \[\left\lfloor \frac{999}{n} \right\rfloor + 1 = \left\lfloor \frac{1000}{n} \right\rfloor.\]

Let's analyze the first equation of these two. This equation is equivalent to the statement that there is a positive integer $a$ such that \[\frac{998}{n} < a \leq \frac{999}{n} \implies 998 < an \leq 999 \implies an = 999 \implies a = \frac{999}{n} \implies n | 999.*\] Analogously, the second equation implies that \[n | 1000.\] So our only $n$ that satisfy this condition are $n \neq 1$ that divide $999$ or $1000$. Using the method to find the number of divisors of a number, we see that $999$ has $8$ divisors and $1000$ has $16$ divisors. Their only common factor is $1$, so there are $8+16-1 = 23$ positive integers that divide either $999$ or $1000$. Since the integer $1$ is a special case and does not count, we must subtract this from our $23$, so our final answer is $23-1 = \boxed{\textbf{(A) } 22}.$

*While this observation may seem strange, it is actually "trivial by intuition" to go straight from $\left\lfloor \frac{998}{n} \right\rfloor + 1 = \left\lfloor \frac{999}{n} \right\rfloor$ to $n | 999$. In fact, "trivial by intuition" is basically a good summary of the solution to this entire problem.

~ihatemath123

Solution 2

Writing out $n = 1, 2, 3, 4 ... 11$, we see that the answer cannot be more than the number of divisors of $998, 999, 1000$ since all $n$ satisfying the problem requirements are among the divisors of $998, 999, 1000$. There are $28$ total divisors, and we subtract $3$ from the start because we count $1$, which never works, thrice.

From the divisors of $998$, note that $499$ and $998$ don't work. $2$ to subtract. Also note that we count $2$ twice, in $998$ and $1000$, so we have to subtract another from the running total of $25$.

Already, we are at $22$ divisors so we conclude that the answer is $\boxed{\textbf{(A)}22}$.

Solution 3

First, we notice the following lemma:

$\textbf{Lemma}$: For $N, n \in \mathbb{N}$, $\left\lfloor \frac{N}{n} \right\rfloor = \left\lfloor \frac{N-1}{n} \right\rfloor + 1$ if $n \mid N$; and $\left\lfloor \frac{N}{n} \right\rfloor = \left\lfloor \frac{N-1}{n} \right\rfloor$ if $n \nmid N.$

$\textbf{Proof}$: Let $A = kn + r$, with $0 \leq r < n$. If $n \mid N$, then $r = 0$. Hence $\left\lfloor \frac{N}{n} \right\rfloor = k$, $\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$, and $\left\lfloor \frac{N}{n} \right\rfloor = \left\lfloor \frac{N-1}{n} \right\rfloor + 1.$

If $n \nmid N$, then $1 \leq r < n$. Hence $\left\lfloor \frac{N}{n} \right\rfloor = k$, $\left\lfloor \frac{N-1}{n} \right\rfloor = k + \left\lfloor \frac{r-1}{n} \right\rfloor = k$, and $\left\lfloor \frac{N}{n} \right\rfloor = \left\lfloor \frac{N-1}{n} \right\rfloor.$

From the lemma and the given equation, we have four possible cases: \[\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)\] \[\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)\] \[\left\lfloor \frac{998}{n} \right\rfloor + 1 = \left\lfloor \frac{999}{n} \right\rfloor = \left\lfloor \frac{1000}{n} \right\rfloor \qquad (3)\] \[\left\lfloor \frac{998}{n} \right\rfloor = \left\lfloor \frac{999}{n} \right\rfloor = \left\lfloor \frac{1000}{n} \right\rfloor \qquad (4)\]

Note that cases (2) and (3) are the cases in which the term, $\left\lfloor \frac{998}{n} \right\rfloor + \left\lfloor \frac{999}{n} \right\rfloor + \left\lfloor \frac{1000}{n} \right\rfloor,$ is not divisible by $3$. 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 $n \mid 1000$ and $n \nmid 999.$ Hence $n$ can be any factor of $1000$ except for $n = 1$. Since $1000 = 2^3 * 5^3,$ there are $(3+1)(3+1) - 1 = 15$ possible values of $n$ for this case.

Case (3): By the lemma, we have $n \mid 999$ and $n \nmid 998.$ Hence $n$ can be any factor of $999$ except for $n = 1$. Since $999 = 3^3 * 37^1,$ there are $(3+1)(1+1) - 1 = 7$ possible values of $n$ for this case.

So in total, we have total of $15+7=\boxed{\textbf{(A)}22}$ possible $n$'s.

~mathboywannabe

Solution 4

Note that $\left\lfloor \frac{998}{n} \right\rfloor + \left\lfloor \frac{999}{n} \right\rfloor + \left\lfloor \frac{1000}{n} \right\rfloor$ is a multiple of $3$ if $\left\lfloor \frac{998}{n} \right\rfloor + \left\lfloor \frac{999}{n} \right\rfloor + \left\lfloor \frac{1000}{n} \right\rfloor$ lies between two consecutive multiples of $n$.


$\textbf{Explanation:}$


Let's assume that the above expression does indeed lie betweent two consecutive multiples of $n$. This implies that $n$ does not divide either $998, 999$ or $1000$, meaning that when divided by $n$, none of the quotients are whole. In turn, this also means that they will all have the same whole number part.


If $\frac{998}{n}, \frac{999}{n},$ and $\frac{1000}{n}$ were to have a different whole number part, then $n$ would have to lie within $998$ and $1000$. If this is confusing, think of why $\frac{6}{5}, \frac{7}{5}$ and $\frac{8}{5}$ have the same whole number part ($1$ in this case). Here, $n=5$. What happens to the whole number part when $n=7$?


Since $\frac{998}{n}, \frac{999}{n},$ and $\frac{1000}{n}$ 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 $k$ be the number we get when we floor $\frac{998}{n}, \frac{999}{n},$ or $\frac{1000}{n}$ if the three of those numbers lie between two consecutive multiples of $n$. Adding them up, we get $3k$ (due to their floors being the same), which is a mulutiple of $3$. So no matter what, we cannot have $\frac{998}{n}, \frac{999}{n},$ and $\frac{1000}{n}$ lie between two consecutive multiples of $n$.


What does this mean? It means that there must be some multiple of $n$ 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.


$\textbf{Case 1}$


Let's assume that the multiple of $n$ is located at $\frac{998}{n}$. Luckily, the only prime factors of $998$ are $2$ and $499$.


We can observe that $499$ doesn't work, since $\frac{998}{499}$ and $\frac{1000}{499}$ will both round down to $2$ when divided by it. However, $2$ does work, since it divides both $998$ and $1000$. The floor of $\frac{999}{2}$ is $499$, , meaning that when we evaluate the given expression for $n=2$, we will get $2\cdot{499}+500$ which isn't a multiple of $3$.


This case works because we have a multiple of $n$ at the end of the expression, as well as the beginning, so the whole number parts of $998, 999$ and $1000$ when divided by $n$ are not all the same, due to $n$ dividing two of these numbers.

The restriction of $n$ 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 $1$ is complete, and we've found that only $2$ works.


$\textbf{Case 2}$

Now, let's assume that the multiple of $n$ is located at $\frac{999}{n}$. In this case, if $n$ divides $999$, it doesn't divide $998$ (since two multiples of a number greater than $1$ are never consecutive), nor does it divide $1000$, for the same reason.


The prime factorization of $999$ is $3^3\cdot37$, and thus has $(3+1)(1+1)=8$ divisors.


When testing a few values of $n$ initially, we observed that $n=1$ causes the expression to be divisible by $3$. Subtracting $1$, we see that there are $7$ values of $n$ that work for this case.


$\textbf{Case 3}$

Finally, let's assume that the multiple of $n$ is located at $\frac{1000}{n}.$


Our goal is to have the other multiple of $n$ below whatever $\frac{998}{n}$ is, so we won't have identical floors throughout the expression.


Once again, any factor of $1000$, except for $2$ is relatively prime to both $998$ and $999$, so when we floor those two numbers, we get an integer that isn't $500$.


$1000$ factors as $2^3\cdot{5^3}$, meaning that it has $(3+1)(3+1)=16$ divisors. $1$ and $2$ either don't work or have already been counted, so there are $14$ valid values of $n$ for this case.


$\textbf{Ending}$


Adding these three cases, we get $1+7+14= \boxed{\textbf{A) }22}$ values of $n$.

-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

2020 AMC 10A (ProblemsAnswer KeyResources)
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. AMC logo.png