Difference between revisions of "2019 AMC 10A Problems/Problem 25"
m (→Solution 2) |
(→See Also) |
||
(18 intermediate revisions by 8 users not shown) | |||
Line 7: | Line 7: | ||
<math>\textbf{(A) } 31 \qquad \textbf{(B) } 32 \qquad \textbf{(C) } 33 \qquad \textbf{(D) } 34 \qquad \textbf{(E) } 35</math> | <math>\textbf{(A) } 31 \qquad \textbf{(B) } 32 \qquad \textbf{(C) } 33 \qquad \textbf{(D) } 34 \qquad \textbf{(E) } 35</math> | ||
− | ==Solution 1== | + | ==Solution== |
+ | ===Solution 1=== | ||
The main insight is that | The main insight is that | ||
Line 16: | Line 17: | ||
<cmath>\frac{(n^2-1)!}{(n!)^n}=\frac{(n^2)!}{(n!)^{n+1}}\cdot\frac{n!}{n^2}</cmath> | <cmath>\frac{(n^2-1)!}{(n!)^n}=\frac{(n^2)!}{(n!)^{n+1}}\cdot\frac{n!}{n^2}</cmath> | ||
− | is an integer if <math>n^2 \mid n!</math>, or in other words, if <math>n \mid (n-1)!</math>. This condition is false precisely when <math>n=4</math> or <math>n</math> is prime, by [[Wilson's Theorem]]. There are <math>15</math> primes between <math>1</math> and <math>50</math>, inclusive, so there are 15 + 1 = 16 terms for which | + | is an integer if <math>n^2 \mid n!</math>, or in other words, if <math>n \mid (n-1)!</math>. This condition is false precisely when <math>n=4</math> or <math>n</math> is prime, by [[Wilson's Theorem]]. There are <math>15</math> primes between <math>1</math> and <math>50</math>, inclusive, so there are <math>15 + 1 = 16</math> terms for which |
<cmath>\frac{(n^2-1)!}{(n!)^{n}}</cmath> | <cmath>\frac{(n^2-1)!}{(n!)^{n}}</cmath> | ||
− | is potentially not an integer. It can be easily verified that the above expression is not an integer for <math>n=4</math> as there are more factors of 2 in the denominator than the numerator. Similarly, it can be verified that the above expression is not an integer for any prime <math>n=p</math>, as there are more factors of p in the denominator than the numerator. Thus all 16 values of n make the expression not an integer and the answer is <math>50-16=\boxed{\ | + | is potentially not an integer. It can be easily verified that the above expression is not an integer for <math>n=4</math> as there are more factors of <math>2</math> in the denominator than the numerator. Similarly, it can be verified that the above expression is not an integer for any prime <math>n=p</math>, as there are more factors of p in the denominator than the numerator. Thus all <math>16</math> values of n make the expression not an integer and the answer is <math>50-16=\boxed{\textbf{(D)}\ 34}</math>. |
− | ==Solution 2== | + | ===Solution 2=== |
− | We can use the P-Adic Valuation of n to solve this problem (recall the P-Adic Valuation of 'n' is denoted by <math>v_p (n)</math> and is defined as the greatest power of some prime 'p' that divides n. For example, <math>v_2 (6)=1</math> or <math>v_7 (245)=2</math> .) Using Legendre's formula, we know that : | + | We can use the P-Adic Valuation (more info could be found here: [[Mathematicial notation]]) of n to solve this problem (recall the P-Adic Valuation of 'n' is denoted by <math>v_p (n)</math> and is defined as the greatest power of some prime 'p' that divides n. For example, <math>v_2 (6)=1</math> or <math>v_7 (245)=2</math> .) Using Legendre's formula, we know that : |
<cmath> v_p (n!)= \sum_{i=1}^\infty \lfloor \frac {n}{p^i} \rfloor </cmath> | <cmath> v_p (n!)= \sum_{i=1}^\infty \lfloor \frac {n}{p^i} \rfloor </cmath> | ||
Line 50: | Line 51: | ||
Then we get: | Then we get: | ||
− | <cmath> p^2 \cdot v_p (p!) \le v_p ((n^4 -1)!) \Longrightarrow p^3 + p^2 \le p^3 + p^2 + p -3 </cmath> Which is true for all primes except for 2, so <math>2^2 = 4</math> doesn't work. It can easily be verified that for all <math>n=p^i</math> where <math>i</math> is an integer greater than 2, satisfies the inequality :<cmath> n \cdot v_p (n!) \le v_p ((n^2 -1 )!)</cmath> | + | <cmath> p^2 \cdot v_p (p!) \le v_p ((n^4 -1)!) \Longrightarrow p^3 + p^2 \le p^3 + p^2 + p -3 </cmath> Which is true for all primes except for 2, so <math>2^2 = 4</math> doesn't work. It can easily be verified that for all <math>n=p^i</math> where <math>i</math> is an integer greater than 2, satisfies the inequality :<cmath> n \cdot v_p (n!) \le v_p ((n^2 -1 )!).</cmath> |
Therefore, there are 16 values that don't work and <math> 50-16 = \boxed{\mathbf{(D)}\ 34}</math> values that work. | Therefore, there are 16 values that don't work and <math> 50-16 = \boxed{\mathbf{(D)}\ 34}</math> values that work. | ||
~qwertysri987 | ~qwertysri987 | ||
+ | |||
+ | ==Solution 3== | ||
+ | Complementary Counting. Looking at the problem, it says that it is from 1-50 inclusive. Worst case, we'll have to check through all of them. First, try plugging in some numbers and you find that 2,3,4,5(all the primes and 4) don't work. There are 15 primes less than 50, and add 1 because of the 4. There are 16 cases, and you subtract them from 50. <math>50-16=\boxed{\textbf{(D) } 34}</math> | ||
+ | |||
==See Also== | ==See Also== | ||
+ | Video Solution by Richard Rusczyk: | ||
+ | https://www.youtube.com/watch?v=9klaWnZojq0 | ||
{{AMC10 box|year=2019|ab=A|num-b=24|after=Last Problem}} | {{AMC10 box|year=2019|ab=A|num-b=24|after=Last Problem}} | ||
{{AMC12 box|year=2019|ab=A|num-b=23|num-a=25}} | {{AMC12 box|year=2019|ab=A|num-b=23|num-a=25}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 21:51, 6 January 2021
- The following problem is from both the 2019 AMC 10A #25 and 2019 AMC 12A #24, so both problems redirect to this page.
Problem
For how many integers between and , inclusive, is an integer? (Recall that .)
Solution
Solution 1
The main insight is that
is always an integer. This is true because it is precisely the number of ways to split up objects into unordered groups of size . Thus,
is an integer if , or in other words, if . This condition is false precisely when or is prime, by Wilson's Theorem. There are primes between and , inclusive, so there are terms for which
is potentially not an integer. It can be easily verified that the above expression is not an integer for as there are more factors of in the denominator than the numerator. Similarly, it can be verified that the above expression is not an integer for any prime , as there are more factors of p in the denominator than the numerator. Thus all values of n make the expression not an integer and the answer is .
Solution 2
We can use the P-Adic Valuation (more info could be found here: Mathematicial notation) of n to solve this problem (recall the P-Adic Valuation of 'n' is denoted by and is defined as the greatest power of some prime 'p' that divides n. For example, or .) Using Legendre's formula, we know that :
Seeing factorials involved in the problem, this prompts us to use Legendre's formula where n is a power of a prime.
We also know that , . Knowing that if , we have that :
and we must find all n for which this is true.
If we plug in , by Legendre's we get two equations:
And we also get :
But we are asked to prove that which is false for all 'n' where n is prime.
Now we try the same for , where p is a prime. By Legendre we arrive at:
and
Then we get:
Which is true for all primes except for 2, so doesn't work. It can easily be verified that for all where is an integer greater than 2, satisfies the inequality :
Therefore, there are 16 values that don't work and values that work.
~qwertysri987
Solution 3
Complementary Counting. Looking at the problem, it says that it is from 1-50 inclusive. Worst case, we'll have to check through all of them. First, try plugging in some numbers and you find that 2,3,4,5(all the primes and 4) don't work. There are 15 primes less than 50, and add 1 because of the 4. There are 16 cases, and you subtract them from 50.
See Also
Video Solution by Richard Rusczyk: https://www.youtube.com/watch?v=9klaWnZojq0
2019 AMC 10A (Problems • Answer Key • Resources) | ||
Preceded by Problem 24 |
Followed by Last Problem | |
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 |
2019 AMC 12A (Problems • Answer Key • Resources) | |
Preceded by Problem 23 |
Followed by Problem 25 |
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 12 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.