Difference between revisions of "2020 AMC 10A Problems/Problem 22"
(→Solution (Casework)) |
(→Solution (Casework)) |
||
Line 46: | Line 46: | ||
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>. | 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> | + | |
+ | <math>999</math> = <math>3^3 \cdot 37^1</math>. | ||
So, the total number of factors of <math>999</math> is <math>4 \cdot 2 = 8</math>. | So, the total number of factors of <math>999</math> is <math>4 \cdot 2 = 8</math>. | ||
Line 58: | Line 59: | ||
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>. | 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>1000</math> = <math>5^3 \cdot 2^3</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>. | So, the total number of factors of <math>1000</math> is <math>4 \cdot 4 = 16</math>. | ||
Revision as of 22:19, 1 February 2020
Problem
For how many positive integers isnot divisible by ? (Recall that is the greatest integer less than or equal to .)
Solution (Casework)
Expression:
Solution:
Let
Notice that for every integer ,
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 ,
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 .
This is due to the fact that , , and do not collectively share any common factors (other than 1).
Note that doesn't work; to prove this, we just have to substitute for in the expression.
This gives us
which is divisible by 3.
Therefore, the case does not work.
Now, we test the four cases listed above.
Case 1: divides
The three terms in the expression must be , as mentioned above, so the sum is , which is divisible by . Therefore, the first case does not work.
Case 2: 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 doesn't work, as mentioned previously.
We now do the same for the third case.
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 .
Again, we have to subtract , for the reason stated in Case 2.
Case 4: divides none of {}
If does not divide {}, then the value of the terms of the above expression are . See if you can figure out why, although the explanation is similar to that of Case 1.
Therefore, the value of the expression 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
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.