Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2019 AMC 10A Problems/Problem 25"

(→‎See Also)
(→‎Solution 3 (Fakesolve))
(16 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==
+
==Solution 1==
−
===Solution 1===
 
 
The main insight is that  
 
The main insight is that  
  
Line 17: Line 16:
 
<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 <math>15 + 1 = 16</math> terms for which
+
is an integer if <math>n^2 \mid n!</math>, or in other words, if <math>\frac{(n-1)!}{n}</math>, is an integer. 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>
Line 23: Line 22:
 
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>.
 
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===
+
SideNote: Another method to prove that <cmath>\frac{(n^2)!}{(n!)^{n+1}}</cmath> is always an integer is instead as follows using Number Theory. Notice that <math>n</math> will divide the numerator <math>n+1</math> times, since <math>n^2 = n \times n</math> contains not one but two factors of <math>n.</math> Also, for <math>a < n,</math> notice that <math>a</math> divides <math>(n^2)!</math> at least <cmath>\lfloor \frac{n^2}{a} \rfloor \ge \lfloor \frac{n^2}{n-1} \rfloor \ge \lfloor \frac{n^2 - 1}{n-1} \rfloor \ge n+1</cmath> times. Thus, each integer from <math>1</math> to <math>n</math> will divide <math>(n^2)!</math> at least <math>n+1</math> times, which proves such a lemma. <math>\square{}</math>
 +
 
 +
==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 <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>
  
−
Seeing factorials involved in the problem, this prompts us to use Legendre's formula where n is a power of a prime.
+
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 , <math>v_p (m^n) = n \cdot v_p (m)</math> .
 
We also know that , <math>v_p (m^n) = n \cdot v_p (m)</math> .
Line 47: Line 48:
 
Now we try the same for <math>n=p^2</math> , where p is a prime. By Legendre we arrive at:
 
Now we try the same for <math>n=p^2</math> , where p is a prime. By Legendre we arrive at:
  
−
<cmath>v_p ((p^4 -1)!) = p^3 + p^2 + p -3</cmath> and <cmath>p^2 \cdot v_p (p^2 !) = p^3 + p^2 </cmath>
+
<cmath>v_p ((p^4 -1)!) = p^3 + p^2 + p -3</cmath>
 +
 
 +
(as <math>v_p(p^4!) = p^3 + p^2 + p + 1</math> and <math>p^4</math> contains 4 factors of <math>p</math>) and
 +
 
 +
<cmath>p^2 \cdot v_p (p^2 !) = p^3 + p^2 </cmath>
  
 
Then we get:
 
Then we get:
Line 57: Line 62:
 
~qwertysri987
 
~qwertysri987
  
−
==Solution 3==
+
==Solution 3 (Non-Rigorous)==
−
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>
+
Notice all <math>15</math> primes don't work as there are <math>n</math> factors of <math>n</math> in the denominator and <math>n-1</math> factors of <math>n</math> in the numerator. Further experimentation finds that <math>n=4</math> does not work as there are 11 factors of 2 in the numerator and 12 in the denominator. We also find that it seems that all other values of <math>n</math> work. So we get <math>50-15-1=\boxed{34}</math> and that happens to be right.
  
 +
~[[BS2012]]
  
 
==See Also==
 
==See Also==

Revision as of 14:21, 11 November 2023

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 $n$ between $1$ and $50$, inclusive, is \[\frac{(n^2-1)!}{(n!)^n}\] an integer? (Recall that $0! = 1$.)

$\textbf{(A) } 31 \qquad \textbf{(B) } 32 \qquad \textbf{(C) } 33 \qquad \textbf{(D) } 34 \qquad \textbf{(E) } 35$

Solution 1

The main insight is that

\[\frac{(n^2)!}{(n!)^{n+1}}\]

is always an integer. This is true because it is precisely the number of ways to split up $n^2$ objects into $n$ unordered groups of size $n$. Thus,

\[\frac{(n^2-1)!}{(n!)^n}=\frac{(n^2)!}{(n!)^{n+1}}\cdot\frac{n!}{n^2}\]

is an integer if $n^2 \mid n!$, or in other words, if $\frac{(n-1)!}{n}$, is an integer. This condition is false precisely when $n=4$ or $n$ is prime, by Wilson's Theorem. There are $15$ primes between $1$ and $50$, inclusive, so there are $15 + 1 = 16$ terms for which

\[\frac{(n^2-1)!}{(n!)^{n}}\]

is potentially not an integer. It can be easily verified that the above expression is not an integer for $n=4$ 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 $n=p$, 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 $50-16=\boxed{\textbf{(D)}\ 34}$.

SideNote: Another method to prove that \[\frac{(n^2)!}{(n!)^{n+1}}\] is always an integer is instead as follows using Number Theory. Notice that $n$ will divide the numerator $n+1$ times, since $n^2 = n \times n$ contains not one but two factors of $n.$ Also, for $a < n,$ notice that $a$ divides $(n^2)!$ at least \[\lfloor \frac{n^2}{a} \rfloor \ge \lfloor \frac{n^2}{n-1} \rfloor \ge \lfloor \frac{n^2 - 1}{n-1} \rfloor \ge n+1\] times. Thus, each integer from $1$ to $n$ will divide $(n^2)!$ at least $n+1$ times, which proves such a lemma. $\square{}$

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 $v_p (n)$ and is defined as the greatest power of some prime 'p' that divides n. For example, $v_2 (6)=1$ or $v_7 (245)=2$ .) Using Legendre's formula, we know that :

\[v_p (n!)= \sum_{i=1}^\infty \lfloor \frac {n}{p^i} \rfloor\]

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 , $v_p (m^n) = n \cdot v_p (m)$ . Knowing that $a\mid b$ if $v_p (a) \le v_p (b)$ , we have that :

\[n \cdot v_p (n!) \le v_p ((n^2 -1 )!)\] and we must find all n for which this is true.

If we plug in $n=p$, by Legendre's we get two equations:

\[v_p ((n^2 -1)!) = \sum_{i=1}^\infty \lfloor \frac {n^2 -1}{p^i} \rfloor = (p-1)+0+...+0 = p-1\]

And we also get :

\[v_p ((n!)^n) = n \cdot v_p (n!)= n \cdot \sum_{i=1}^\infty \lfloor \frac {n}{p^i} \rfloor = p \cdot ( 1+0+...0) = p\]

But we are asked to prove that $n \cdot v_p (n!) \le v_p ((n^2 -1 )!) \Longrightarrow p \le p-1$ which is false for all 'n' where n is prime.

Now we try the same for $n=p^2$ , where p is a prime. By Legendre we arrive at:

\[v_p ((p^4 -1)!) = p^3 + p^2 + p -3\]

(as $v_p(p^4!) = p^3 + p^2 + p + 1$ and $p^4$ contains 4 factors of $p$) and

\[p^2 \cdot v_p (p^2 !) = p^3 + p^2\]

Then we get:

\[p^2 \cdot v_p (p!) \le v_p ((n^4 -1)!) \Longrightarrow p^3 + p^2 \le p^3 + p^2 + p -3\] Which is true for all primes except for 2, so $2^2 = 4$ doesn't work. It can easily be verified that for all $n=p^i$ where $i$ is an integer greater than 2, satisfies the inequality :\[n \cdot v_p (n!) \le v_p ((n^2 -1 )!).\]

Therefore, there are 16 values that don't work and $50-16 = \boxed{\mathbf{(D)}\ 34}$ values that work.

~qwertysri987

Solution 3 (Non-Rigorous)

Notice all $15$ primes don't work as there are $n$ factors of $n$ in the denominator and $n-1$ factors of $n$ in the numerator. Further experimentation finds that $n=4$ does not work as there are 11 factors of 2 in the numerator and 12 in the denominator. We also find that it seems that all other values of $n$ work. So we get $50-15-1=\boxed{34}$ and that happens to be right.

~BS2012

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_AMC_10A_Problems/Problem_25&oldid=202340"