Art of Problem Solving
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

2023 AMC 10B Problems/Problem 15: Difference between revisions

← Older edit
Michaelwenquan (talk | contribs)
editor
88 edits
added another solution
Zzzzzzzzzzzzz (talk | contribs)
editor
1 edit
No edit summary
 
(18 intermediate revisions by 6 users not shown)
Line 1: Line 1:
==Problem==
==Problem==
What is the least positive integer <math>m</math> such that <math>m\cdot2!\cdot3!\cdot4!\cdot5!...16!</math> is a perfect square?
What is the least positive integer <imath>m</imath> such that <imath>m\cdot2!\cdot3!\cdot4!\cdot5!...16!</imath> is a perfect square?


<math>\textbf{(A) }30\qquad\textbf{(B) }30030\qquad\textbf{(C) }70\qquad\textbf{(D) }1430\qquad\textbf{(E) }1001</math>
<imath>\textbf{(A) }30\qquad\textbf{(B) }30030\qquad\textbf{(C) }70\qquad\textbf{(D) }1430\qquad\textbf{(E) }1001</imath>
==Video Solution by MegaMath==
 
https://www.youtube.com/watch?v=le0KSx3Cy-g&t=28s


== Solution 1 ==
== Solution 1 ==


We want <math>m\cdot2!\cdot3!\cdot4!\cdot\dots\cdot16!</math> to be a perfect square. Notice that we can rewrite and pair up certain elements:  
We want <imath>m\cdot2!\cdot3!\cdot4!\cdot\dots\cdot16!</imath> to be a perfect square. Notice that we can rewrite and pair up certain elements:  


<cmath>m\cdot2\cdot3!\cdot(4\cdot3!)\cdot5!\cdot(6\cdot5!)\cdot\dots\cdot15!\cdot(16\cdot15!)=m\cdot2\cdot4\cdot6\cdot\dots\cdot16\cdot(3!)^2(5!)^2\cdot\dots\cdot(15!)^2.</cmath>
<cmath>m\cdot2\cdot3!\cdot(4\cdot3!)\cdot5!\cdot(6\cdot5!)\cdot\dots\cdot15!\cdot(16\cdot15!)=m\cdot2\cdot4\cdot6\cdot\dots\cdot16\cdot(3!)^2(5!)^2\cdot\dots\cdot(15!)^2.</cmath>


Note here that this is equivalent to simply <math>m\cdot2\cdot4\cdot\dots\cdot16</math> being a perfect square (this is intuitively obvious: i.e. if <math>a=bc</math> is a perfect square and so is <math>b</math>, then of course <math>c</math> must be a perfect square too). We can rewrite this as the following:  
Note here that this is equivalent to simply <imath>m\cdot2\cdot4\cdot\dots\cdot16</imath> being a perfect square (this is intuitively obvious: i.e. if <imath>a=bc</imath> is a perfect square and so is <imath>b</imath>, then of course <imath>c</imath> must be a perfect square too). We can rewrite this as the following:  


<cmath>m\cdot2^8\cdot(1\cdot2\cdot3\cdot\dots\cdot8)\equiv m\cdot2\cdot3\cdot4\cdot5\cdot6\cdot7\cdot8\equiv m\cdot70.</cmath>
<cmath>m\cdot2^8\cdot(1\cdot2\cdot3\cdot\dots\cdot8)\equiv m\cdot2\cdot3\cdot4\cdot5\cdot6\cdot7\cdot8\equiv m\cdot70.</cmath>


The smallest <math>m</math> s.t. <math>70m</math> is a perfect square is, of course, <math>70</math> itself. QED.  
The smallest <imath>m</imath> s.t. <imath>70m</imath> is a perfect square is, of course, <imath>70</imath> itself. QED.  


~Technodoggo (rewritten as of 2024)
~Technodoggo (rewritten as of 2024)


== Solution 2 ==
== Solution 2 ==
Perfect squares have all of the powers in their prime factorization even. To evaluate <math>2!\cdot3!\cdot4!\cdot5!...16!</math> we get the following:
Perfect squares have all of the powers in their prime factorization even. To evaluate <imath>2!\cdot3!\cdot4!\cdot5!...16!</imath> we get the following:


<math>(2^{15}) \times (3^{14}) \times ((2^2)^{13}) \times (5^{12}) \times ((2 \times 3)^{11}) \times (7^{10}) \times ((2^3)^{9}) \times ((3^2)^8) \times \\ ((5 \times 2)^7) \times (11^6) \times (((2^2) \times 3)^5) \times (13^4) \times ((7 \times 2)^3) \times ((3 \times 5)^2) \times ((2^4)^1)</math>.
<imath>(2^{15}) \times (3^{14}) \times ((2^2)^{13}) \times (5^{12}) \times ((2 \times 3)^{11}) \times (7^{10}) \times ((2^3)^{9}) \times ((3^2)^8) \times \\ ((5 \times 2)^7) \times (11^6) \times (((2^2) \times 3)^5) \times (13^4) \times ((7 \times 2)^3) \times ((3 \times 5)^2) \times ((2^4)^1)</imath>.


Taking all powers <math>\mod 2</math> we get:
Taking all powers <imath>\mod 2</imath> we get:


<math>(2^1) \times ((2 \times 3)^1) \times (2^1) \times ((5 \times 2)^1) \times (3^1) \times ((7 \times 2)^1)</math>
<imath>(2^1) \times ((2 \times 3)^1) \times (2^1) \times ((5 \times 2)^1) \times (3^1) \times ((7 \times 2)^1)</imath>


Simplifying again, we finally get:
Simplifying again, we finally get:


<math>(2^1) \times (5^1) \times (7^1)</math>
<imath>(2^1) \times (5^1) \times (7^1)</imath>


To make all the powers left even, we need to multiply by <math>(2 \times 5 \times 7)</math> which is <math>\boxed{\text{(C) }  70}</math>.
To make all the powers left even, we need to multiply by <imath>(2 \times 5 \times 7)</imath> which is <imath>\boxed{\text{(C) }  70}</imath>.


~darrenn.cp  
~darrenn.cp  
Line 41: Line 38:


We can prime factorize the solutions:  
We can prime factorize the solutions:  
A = <math>2 \cdot 3 \cdot 5,</math>  
A = <imath>2 \cdot 3 \cdot 5,</imath>  
B = <math>2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13, </math>
B = <imath>2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13, </imath>
C = <math>2 \cdot 5 \cdot 7, </math>
C = <imath>2 \cdot 5 \cdot 7, </imath>
D = <math>2 \cdot 5 \cdot 11 \cdot 13, </math>
D = <imath>2 \cdot 5 \cdot 11 \cdot 13, </imath>
E = <math>7 \cdot 11 \cdot 13,  
E = <imath>7 \cdot 11 \cdot 13,  
</math>
</imath>


We can immediately eliminate B, D, and E since 13 only appears in <math>13!, 14!, 15, 16!</math>, so <math>13\cdot 13\cdot 13\cdot 13</math> is a perfect square.
We can immediately eliminate B, D, and E since 13 only appears in <imath>13!, 14!, 15, 16!</imath>, so <imath>13\cdot 13\cdot 13\cdot 13</imath> is a perfect square.
Next, we can test if 7 is possible (and if it is not we can use process of elimination).
Next, we can test if 7 is possible (and if it is not we can use process of elimination).
7 appears in <math>7!</math> to <math>16!</math> and
7 appears in <imath>7!</imath> to <imath>16!</imath> and
14 appears in <math>14!</math> to <math>16!</math>.  
14 appears in <imath>14!</imath> to <imath>16!</imath>.  
So, there is an odd amount of 7's since there are 10 7's from <math>7!</math> to <math>16!</math> and 3 7's from <math>14!</math> to <math>16!</math> since 7 appears in 14 once, and <math>10+3=13</math> which is odd. So we need to multiply by 7 to get a perfect square. Since 30 is not a divisor of 7, our answer is 70 which is <math>\boxed{\text{C}}</math>.
So, there is an odd amount of 7's since there are 10 7's from <imath>7!</imath> to <imath>16!</imath> and 3 7's from <imath>14!</imath> to <imath>16!</imath> since 7 appears in 14 once, and <imath>10+3=13</imath> which is odd. So we need to multiply by 7 to get a perfect square. Since 30 is not a divisor of 7, our answer is 70 which is <imath>\boxed{\text{C}}</imath>.


~aleyang
~aleyang
Line 58: Line 55:
== Solution 4 ==
== Solution 4 ==


First, we note that <math>3! = 2! \cdot 3</math>, <math>5! = 4! \cdot 5, ... 15! = 14! \cdot 15</math>. So, <math>2!\cdot3! ={2!}^2\cdot3 \equiv 3, 4!\cdot5!={4!}^2\cdot5 \equiv 5, ... 14!\cdot15!={14!}^2\cdot15\equiv15</math>. Simplifying the whole sequence and cancelling out the squares, we get <math>3 \cdot 5 \cdot 7 \cdot 9 \cdot 11 \cdot 13 \cdot 15 \cdot 16!</math>. Prime factoring <math>16!</math> and cancelling out the squares, the only numbers that remain are <math>2, 5,</math> and <math>7</math>. Since we need to make this a perfect square, <math>m = 2 \cdot 5 \cdot 7</math>. Multiplying this out, we get <math>\boxed{\text{(C) }  70}</math>.
First, we note that <imath>3! = 2! \cdot 3</imath>, <imath>5! = 4! \cdot 5, ... 15! = 14! \cdot 15</imath>. So, <imath>2!\cdot3! ={2!}^2\cdot3 \equiv 3, 4!\cdot5!={4!}^2\cdot5 \equiv 5, ... 14!\cdot15!={14!}^2\cdot15\equiv15</imath>. Simplifying the whole sequence and cancelling out the squares, we get <imath>3 \cdot 5 \cdot 7 \cdot 9 \cdot 11 \cdot 13 \cdot 15 \cdot 16!</imath>. Prime factoring <imath>16!</imath> and cancelling out the squares, the only numbers that remain are <imath>2, 5,</imath> and <imath>7</imath>. Since we need to make this a perfect square, <imath>m = 2 \cdot 5 \cdot 7</imath>. Multiplying this out, we get <imath>\boxed{\text{(C) }  70}</imath>.


~Stead (a.k.a. Aaron) & ~Technodoggo (add more examples)
~Stead (a.k.a. Aaron) & ~Technodoggo (add more examples)


== Solution 5 (Bashy method) ==
==Solution 5 (Legendre's Formula)==
We know that a perfect square must be in the form <math>2^{2a_1}\cdot3^{2a_2}\cdot5^{2a_3}...p^{2a_n}</math> where <math>a_1, a_2, a_3, ..., a_n</math> are nonnegative integers, and <math>p</math> is the largest and <math>nth</math> prime factor of our square number.
 
We need to find the prime factorization of <imath>16! \cdot 15! \cdot 14! ... \cdot 1!</imath> and check whether the exponents of each prime are odd or even.
 
Using [[Legendre's Formula]] on each of the factorials and adding the powers of each prime we get:
 
Powers of 2:
 
<cmath>15 + 11 + 11 + 10 + 10 + 8 +8 + 7 + 7 + 4 + 4 + 3 + 3 + 1 + 1 + 0 = 103</cmath>
 
Powers of 3:
<cmath>6 + 6 + 5 + 5 + 5 + 3 + 3 + 4 + 2 + 2 + 2 + 1 + 1 + 1 + 0 + 0 = 46</cmath>
 
Powers of 5:
<cmath>3 + 3 + 2 + 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 0 + 0 + 0 + 0 = 23</cmath>
 
Powers of 7:
<cmath>2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 13</cmath>
 
Powers of 11:
<cmath>1 + 1 + 1 + 1 + 1 + 1 = 6</cmath> 
 
Powers of 13:
<cmath>1 + 1 + 1 + 1 = 4</cmath>
 
 
<imath>2, 5,</imath> and <imath>7</imath> have odd exponents, so the answer is <imath>2\cdot 5 \cdot 7 = \boxed{\text{ (C) }70}</imath>.
 
~[https://artofproblemsolving.com/wiki/index.php/User:grogg007 grogg007]
 
== Solution 6 (Bashy method) ==
We know that a perfect square must be in the form <imath>2^{2a_1}\cdot3^{2a_2}\cdot5^{2a_3}...p^{2a_n}</imath> where <imath>a_1, a_2, a_3, ..., a_n</imath> are nonnegative integers, and <imath>p</imath> is the largest and <imath>nth</imath> prime factor of our square number.


Let's assume <math>r=m\cdot2!\cdot3!\cdot4!\cdot5!...16!</math>. We need to prime factorize <math>r</math> and see which prime factors are raised to an odd power. Then, we can multiply one factor each of prime number with an odd number of factors to <math>m</math>. We can do this by finding the number of factors of <math>2</math>, <math>3</math>, <math>5</math>, <math>7</math>, <math>11</math>, and <math>13</math>.
Let's assume <imath>r=m\cdot2!\cdot3!\cdot4!\cdot5!...16!</imath>. We need to prime factorize <imath>r</imath> and see which prime factors are raised to an odd power. Then, we can multiply one factor each of prime number with an odd number of factors to <imath>m</imath>. We can do this by finding the number of factors of <imath>2</imath>, <imath>3</imath>, <imath>5</imath>, <imath>7</imath>, <imath>11</imath>, and <imath>13</imath>.


Case 1: Factors of <math>2</math>
Case 1: Factors of <imath>2</imath>


We first count factors of <math>2^1</math> in each of the factorials. We know there is one factor of <math>2^1</math> each in <math>2!</math> and <math>3!</math>, two in <math>4!</math> and <math>5!</math>, and so on until we have<math>8</math> factors of <math>2^1</math> in <math>16!</math>. Adding them all up, we have <math>1+1+2+2+...7+7+8=64</math>.
We first count factors of <imath>2^1</imath> in each of the factorials. We know there is one factor of <imath>2^1</imath> each in <imath>2!</imath> and <imath>3!</imath>, two in <imath>4!</imath> and <imath>5!</imath>, and so on until we have<imath>8</imath> factors of <imath>2^1</imath> in <imath>16!</imath>. Adding them all up, we have <imath>1+1+2+2+...7+7+8=64</imath>.


Now, we count factors of <math>2^2</math> in each of the factorials. We know there is one factor of <math>2^2</math> each in <math>4!</math>, <math>5!</math>, <math>6!</math>, and <math>7!</math>, two in <math>8!</math>, <math>9!</math>, <math>10</math>, and <math>11!</math>, and so on until we have <math>4</math> factors of <math>2^1</math> in <math>16!</math>. Adding them all up, we have <math>1+1+1+1+2+2+2+2+3+3+3+3+4=28</math>.
Now, we count factors of <imath>2^2</imath> in each of the factorials. We know there is one factor of <imath>2^2</imath> each in <imath>4!</imath>, <imath>5!</imath>, <imath>6!</imath>, and <imath>7!</imath>, two in <imath>8!</imath>, <imath>9!</imath>, <imath>10</imath>, and <imath>11!</imath>, and so on until we have <imath>4</imath> factors of <imath>2^1</imath> in <imath>16!</imath>. Adding them all up, we have <imath>1+1+1+1+2+2+2+2+3+3+3+3+4=28</imath>.


Now we count factors of <math>2^3</math> in each of the factorials. Using a similar method as above, we have a sum of <math>1+1+1+1+1+1+1+1+2=10</math>.
Now we count factors of <imath>2^3</imath> in each of the factorials. Using a similar method as above, we have a sum of <imath>1+1+1+1+1+1+1+1+2=10</imath>.


Now we count factors of <math>2^4</math> in each of the factorials. Using a similar method as above, we have a factor of <math>2^4</math> in <math>16</math>, so there is <math>1</math> factor of <math>2^4</math>.
Now we count factors of <imath>2^4</imath> in each of the factorials. Using a similar method as above, we have a factor of <imath>2^4</imath> in <imath>16</imath>, so there is <imath>1</imath> factor of <imath>2^4</imath>.


Adding all the factors of <math>2</math>, we have <math>103</math>. Since <math>103</math> is odd, <math>m</math> has one factor of <math>2</math>.
Adding all the factors of <imath>2</imath>, we have <imath>103</imath>. Since <imath>103</imath> is odd, <imath>m</imath> has one factor of <imath>2</imath>.


Case 2: Factors of <math>3</math>
Case 2: Factors of <imath>3</imath>


We use a similar method as in case 1. We first count factors of <math>3^1</math>. We obtain the sum <math>1+1+1+2+2+2+...4+4+4+5+5=50</math>.
We use a similar method as in case 1. We first count factors of <imath>3^1</imath>. We obtain the sum <imath>1+1+1+2+2+2+...4+4+4+5+5=50</imath>.


We count factors of <math>3^2</math>. We obtain the sum <math>1+1+1+1+1+1+1+1=8</math>.
We count factors of <imath>3^2</imath>. We obtain the sum <imath>1+1+1+1+1+1+1+1=8</imath>.


Adding all the factors of <math>3</math>, we have <math>58</math>. Since <math>58</math> is even, <math>m</math> has <math>0</math> factors of <math>3</math>.
Adding all the factors of <imath>3</imath>, we have <imath>58</imath>. Since <imath>58</imath> is even, <imath>m</imath> has <imath>0</imath> factors of <imath>3</imath>.


Case 3: Factors of <math>5</math>
Case 3: Factors of <imath>5</imath>


We count the factors of <math>5^1</math>: <math>1+1+1+1+1+2+2+2+2+2+3+3=21</math>. Since <math>21</math> is odd, <math>m</math> has one factor of <math>5</math>.
We count the factors of <imath>5^1</imath>: <imath>1+1+1+1+1+2+2+2+2+2+3+3=21</imath>. Since <imath>21</imath> is odd, <imath>m</imath> has one factor of <imath>5</imath>.


Case 4: Factors of <math>7</math>
Case 4: Factors of <imath>7</imath>


We count the factors of <math>7^1</math>: <math>1+1+1+1+1+1+1+2+2+2=13</math>. Since <math>13</math> is odd, <math>m</math> has one factor of <math>7</math>.
We count the factors of <imath>7^1</imath>: <imath>1+1+1+1+1+1+1+2+2+2=13</imath>. Since <imath>13</imath> is odd, <imath>m</imath> has one factor of <imath>7</imath>.


Case 5: Factors of <math>11</math>
Case 5: Factors of <imath>11</imath>


We count the factors of <math>11^1</math>: <math>1+1+1+1+1+1=6</math>. Since <math>6</math> is even, <math>m</math> has <math>0</math> factors of <math>11</math>.
We count the factors of <imath>11^1</imath>: <imath>1+1+1+1+1+1=6</imath>. Since <imath>6</imath> is even, <imath>m</imath> has <imath>0</imath> factors of <imath>11</imath>.


Case 6: Factors of <math>13</math>
Case 6: Factors of <imath>13</imath>


We count the factors of <math>13^1</math>: <math>1+1+1+1=4</math>. Since <math>4</math> is even, <math>m</math> has <math>0</math> factors of <math>13</math>.
We count the factors of <imath>13^1</imath>: <imath>1+1+1+1=4</imath>. Since <imath>4</imath> is even, <imath>m</imath> has <imath>0</imath> factors of <imath>13</imath>.


Multiplying out all our factors for <math>m</math>, we obtain <math>2\cdot5\cdot7=\boxed{\text{ (C) }70}</math>.
Multiplying out all our factors for <imath>m</imath>, we obtain <imath>2\cdot5\cdot7=\boxed{\text{ (C) }70}</imath>.


~arjken
~arjken


==Solution 6 (Answer Choices)==
==Solution 7 (Answer Choices)==
We see that all the answer choices are divisible by <math>10</math> except for <math>1001</math>, and we also notice that the answer choices have <math>3</math>, <math>7</math>, <math>11</math>, or <math>13</math> as a prime factor.
We see that all the answer choices are divisible by <imath>10</imath> except for <imath>1001</imath>, and we also notice that the answer choices have <imath>3</imath>, <imath>7</imath>, <imath>11</imath>, or <imath>13</imath> as a prime factor.


Testing, we see that <math>3</math>, <math>11</math>, <math>13</math> have an even power in the product, so we have that all the other answer choices will not work.
Testing, we see that <imath>3</imath>, <imath>11</imath>, <imath>13</imath> have an even power in the product, so we have that all the other answer choices will not work.


Therefore we just have <math>\boxed{\text{ (C) }70}</math>.
Therefore we just have <imath>\boxed{\text{ (C) }70}</imath>.


==Solution 7 (Fastest Intuition)==
==Solution 8 (Fastest Intuition)==
Notice that you can add the factor <math>1!</math> to the expression to make it <math>m\cdot1!\cdot2!\cdot3!\cdot4!\cdot5!\cdot6!\cdot7!\cdot8!\cdot9!\cdot10!\cdot11!\cdot12!\cdot13!\cdot14!\cdot15!\cdot16!</math>
Notice that you can add the factor <imath>1!</imath> to the expression to make it <imath>m\cdot1!\cdot2!\cdot3!\cdot4!\cdot5!\cdot6!\cdot7!\cdot8!\cdot9!\cdot10!\cdot11!\cdot12!\cdot13!\cdot14!\cdot15!\cdot16!</imath>


Every consecutive pair <math>n!\cdot(n+1)!</math> can be simplified to <math>n+1</math> (divide out <math>n!^2</math>).
Every consecutive pair <imath>n!\cdot(n+1)!</imath> can be simplified to <imath>n+1</imath> (divide out <imath>n!^2</imath>).


Resulting is the product <math>m\cdot2\cdot4\cdot6\cdot8\cdot10\cdot12\cdot14\cdot16 = m\cdot2^8\cdot8!</math>
Resulting is the product <imath>m\cdot2\cdot4\cdot6\cdot8\cdot10\cdot12\cdot14\cdot16 = m\cdot2^8\cdot8!</imath>


This is easily simplified to <math>m\cdot2\cdot5\cdot7 = m\cdot70</math> when dividing out perfect squares.  
This is easily simplified to <imath>m\cdot2\cdot5\cdot7 = m\cdot70</imath> when dividing out perfect squares.  


This means that <math>m</math> must have at minimun a factor of <math>70</math> which gives answer choice <math>\boxed{\text{ (C) }70}</math>.
This means that <imath>m</imath> must have a minimum factor of <imath>70</imath> which gives answer choice <imath>\boxed{\text{ (C) }70}</imath>.


~coolishu
~coolishu


==Solution 8(Pretty Quick similar to solution 7)==
==Solution 9(Pretty Quick similar to solution 8)==
<math>16!\left(15!\right)</math>
<imath>16!\left(15!\right)</imath>
this can be written as  
this can be written as  
<math>16\left(15!\right)\left(15!\right)</math>
<imath>16\left(15!\right)\left(15!\right)</imath>




Line 136: Line 163:




<math>16\left(15!\right)^{2}</math>
<imath>16\left(15!\right)^{2}</imath>


Now lets try  
Now lets try  


<math>16!15!14!</math>
<imath>16!15!14!</imath>


<math>16\left(15\right)\left(14!\right)15\left(14!\right)\left(14!\right)</math>
<imath>16\left(15\right)\left(14!\right)15\left(14!\right)\left(14!\right)</imath>




thus  
thus  
<math>16\left(15\right)^{2}\left(14\right)^{3}</math>
<imath>16\left(15\right)^{2}\left(14\right)^{3}</imath>




we can continue this pattern until one to get
we can continue this pattern until one to get
<math>m\cdot2!\cdot3!\cdot4!\cdot5!...16! = 16\left(15\right)^{2}\left(14\right)^{3}\left(13\right)^{4}\left(12\right)^{5}\left(11\right)^{6}....\left(1\right)^{15}</math>
<imath>m\cdot2!\cdot3!\cdot4!\cdot5!...16! = 16\left(15\right)^{2}\left(14\right)^{3}\left(13\right)^{4}\left(12\right)^{5}\left(11\right)^{6}....\left(1\right)^{15}</imath>


we can remove all the even powers of expression above to get  
we can remove all the even powers of expression above to get  


<math>16\left(14\right)^{3}\left(12\right)^{5}\left(10\right)^{7}\left(8\right)^{9}\left(6\right)^{11}\left(4\right)^{13}\left(2\right)^{15}</math>
<imath>16\left(14\right)^{3}\left(12\right)^{5}\left(10\right)^{7}\left(8\right)^{9}\left(6\right)^{11}\left(4\right)^{13}\left(2\right)^{15}</imath>




Line 164: Line 191:
30 or 70.
30 or 70.


Then look all the stuff with 7 which would only consist of <math>{14}^3</math>
Then look all the stuff with 7 which would only consist of <imath>{14}^3</imath>


which needs an extra 7 to give it company, so put answer must be divisble by 7 and less than 210
which needs an extra 7 to give it company, so put answer must be divisble by 7 and less than 210
Line 170: Line 197:
which leaves 70 or C as our answer
which leaves 70 or C as our answer


<math>\boxed{\text{ (C) }70}</math>.
<imath>\boxed{\text{ (C) }70}</imath>.


Note: you can also just remove all pairs of two to get <math>16\left(14\right)\left(12\right)\left(10\right)\left(8\right)\left(6\right)\left(4\right)\left(2\right)</math>
Note: you can also just remove all pairs of two to get <imath>16\left(14\right)\left(12\right)\left(10\right)\left(8\right)\left(6\right)\left(4\right)\left(2\right)</imath>


==Solution 9 (Braindead solution)==
==Solution 10 (Braindead solution)==


List out 1 to 16:
List out 1 to 16:
Line 192: Line 219:
<cmath>2^1, 2^1\cdot 3^1, 2^3, 2^1 \cdot 5^1, 2^2 \cdot 3^1, 2^1 \cdot 7^1.</cmath>
<cmath>2^1, 2^1\cdot 3^1, 2^3, 2^1 \cdot 5^1, 2^2 \cdot 3^1, 2^1 \cdot 7^1.</cmath>


We multiply all the terms together and remove perfect squares to get <math>2^1 \cdot 5^1 \cdot 7^1 = \boxed{\text{ (C) }70}</math>.
We multiply all the terms together and remove perfect squares to get <imath>2^1 \cdot 5^1 \cdot 7^1 = \boxed{\text{ (C) }70}</imath>.
 
== Solution 11 ==
 
Note that all prime factors must have an even exponent, and that m must be the multiplied equivalent of all odd-exponent prime factors.  The only prime numbers appearing are  2, 3, 5, 7, 11, and 13.  We can quickly rule out 11 and 13 since they appear 6 and 4 times, respectively.  That leaves 2, 3, 5, and 7.  We can see that 2 numbers are multiples: 30 and 70.  30 is 2*5*3, 70 is 2*5*7.  If we double-check, 3 comes up an even number of times, so our answer is 70.  If there is no time left, this method quickly eliminates enough solutions so that guessing could be preferable to leaving it blank.
 
~Bjartskular457
 
~Zzzzzzzzzzzzz


==Video Solution 2 by OmegaLearn==
==Video Solution 2 by OmegaLearn==
Line 202: Line 237:
==Video Solution 4 by paixiao==
==Video Solution 4 by paixiao==
https://www.youtube.com/watch?v=EvA2Nlb7gi4&t=238s
https://www.youtube.com/watch?v=EvA2Nlb7gi4&t=238s
This video link is invalid now.


==Video Solution==
==Video Solution==
Line 208: Line 244:


~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
==Video Solution by MegaMath==
== https://www.youtube.com/watch?v=le0KSx3Cy-gt=28s ==


==See also==
==See also==
{{AMC10 box|year=2023|ab=B|num-b=14|num-a=16}}
{{AMC10 box|year=2023|ab=B|num-b=14|num-a=16}}
{{MAA Notice}}
{{MAA Notice}}

Latest revision as of 06:59, 11 November 2025

Problem

What is the least positive integer $m$ such that $m\cdot2!\cdot3!\cdot4!\cdot5!...16!$ is a perfect square?

$\textbf{(A) }30\qquad\textbf{(B) }30030\qquad\textbf{(C) }70\qquad\textbf{(D) }1430\qquad\textbf{(E) }1001$

Solution 1

We want $m\cdot2!\cdot3!\cdot4!\cdot\dots\cdot16!$ to be a perfect square. Notice that we can rewrite and pair up certain elements:

\[m\cdot2\cdot3!\cdot(4\cdot3!)\cdot5!\cdot(6\cdot5!)\cdot\dots\cdot15!\cdot(16\cdot15!)=m\cdot2\cdot4\cdot6\cdot\dots\cdot16\cdot(3!)^2(5!)^2\cdot\dots\cdot(15!)^2.\]

Note here that this is equivalent to simply $m\cdot2\cdot4\cdot\dots\cdot16$ being a perfect square (this is intuitively obvious: i.e. if $a=bc$ is a perfect square and so is $b$, then of course $c$ must be a perfect square too). We can rewrite this as the following:

\[m\cdot2^8\cdot(1\cdot2\cdot3\cdot\dots\cdot8)\equiv m\cdot2\cdot3\cdot4\cdot5\cdot6\cdot7\cdot8\equiv m\cdot70.\]

The smallest $m$ s.t. $70m$ is a perfect square is, of course, $70$ itself. QED.

~Technodoggo (rewritten as of 2024)

Solution 2

Perfect squares have all of the powers in their prime factorization even. To evaluate $2!\cdot3!\cdot4!\cdot5!...16!$ we get the following:

$(2^{15}) \times (3^{14}) \times ((2^2)^{13}) \times (5^{12}) \times ((2 \times 3)^{11}) \times (7^{10}) \times ((2^3)^{9}) \times ((3^2)^8) \times \\ ((5 \times 2)^7) \times (11^6) \times (((2^2) \times 3)^5) \times (13^4) \times ((7 \times 2)^3) \times ((3 \times 5)^2) \times ((2^4)^1)$.

Taking all powers $\mod 2$ we get:

$(2^1) \times ((2 \times 3)^1) \times (2^1) \times ((5 \times 2)^1) \times (3^1) \times ((7 \times 2)^1)$

Simplifying again, we finally get:

$(2^1) \times (5^1) \times (7^1)$

To make all the powers left even, we need to multiply by $(2 \times 5 \times 7)$ which is $\boxed{\text{(C) } 70}$.

~darrenn.cp

Solution 3

We can prime factorize the solutions: A = $2 \cdot 3 \cdot 5,$ B = $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13,$ C = $2 \cdot 5 \cdot 7,$ D = $2 \cdot 5 \cdot 11 \cdot 13,$ E = $7 \cdot 11 \cdot 13,$

We can immediately eliminate B, D, and E since 13 only appears in $13!, 14!, 15, 16!$, so $13\cdot 13\cdot 13\cdot 13$ is a perfect square. Next, we can test if 7 is possible (and if it is not we can use process of elimination). 7 appears in $7!$ to $16!$ and 14 appears in $14!$ to $16!$. So, there is an odd amount of 7's since there are 10 7's from $7!$ to $16!$ and 3 7's from $14!$ to $16!$ since 7 appears in 14 once, and $10+3=13$ which is odd. So we need to multiply by 7 to get a perfect square. Since 30 is not a divisor of 7, our answer is 70 which is $\boxed{\text{C}}$.

~aleyang

Solution 4

First, we note that $3! = 2! \cdot 3$, $5! = 4! \cdot 5, ... 15! = 14! \cdot 15$. So, $2!\cdot3! ={2!}^2\cdot3 \equiv 3, 4!\cdot5!={4!}^2\cdot5 \equiv 5, ... 14!\cdot15!={14!}^2\cdot15\equiv15$. Simplifying the whole sequence and cancelling out the squares, we get $3 \cdot 5 \cdot 7 \cdot 9 \cdot 11 \cdot 13 \cdot 15 \cdot 16!$. Prime factoring $16!$ and cancelling out the squares, the only numbers that remain are $2, 5,$ and $7$. Since we need to make this a perfect square, $m = 2 \cdot 5 \cdot 7$. Multiplying this out, we get $\boxed{\text{(C) } 70}$.

~Stead (a.k.a. Aaron) & ~Technodoggo (add more examples)

Solution 5 (Legendre's Formula)

We need to find the prime factorization of $16! \cdot 15! \cdot 14! ... \cdot 1!$ and check whether the exponents of each prime are odd or even.

Using Legendre's Formula on each of the factorials and adding the powers of each prime we get:

Powers of 2:

\[15 + 11 + 11 + 10 + 10 + 8 +8 + 7 + 7 + 4 + 4 + 3 + 3 + 1 + 1 + 0 = 103\]

Powers of 3: \[6 + 6 + 5 + 5 + 5 + 3 + 3 + 4 + 2 + 2 + 2 + 1 + 1 + 1 + 0 + 0 = 46\]

Powers of 5: \[3 + 3 + 2 + 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 0 + 0 + 0 + 0 = 23\]

Powers of 7: \[2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 13\]

Powers of 11: \[1 + 1 + 1 + 1 + 1 + 1 = 6\]

Powers of 13: \[1 + 1 + 1 + 1 = 4\]


$2, 5,$ and $7$ have odd exponents, so the answer is $2\cdot 5 \cdot 7 = \boxed{\text{ (C) }70}$.

~grogg007

Solution 6 (Bashy method)

We know that a perfect square must be in the form $2^{2a_1}\cdot3^{2a_2}\cdot5^{2a_3}...p^{2a_n}$ where $a_1, a_2, a_3, ..., a_n$ are nonnegative integers, and $p$ is the largest and $nth$ prime factor of our square number.

Let's assume $r=m\cdot2!\cdot3!\cdot4!\cdot5!...16!$. We need to prime factorize $r$ and see which prime factors are raised to an odd power. Then, we can multiply one factor each of prime number with an odd number of factors to $m$. We can do this by finding the number of factors of $2$, $3$, $5$, $7$, $11$, and $13$.

Case 1: Factors of $2$

We first count factors of $2^1$ in each of the factorials. We know there is one factor of $2^1$ each in $2!$ and $3!$, two in $4!$ and $5!$, and so on until we have$8$ factors of $2^1$ in $16!$. Adding them all up, we have $1+1+2+2+...7+7+8=64$.

Now, we count factors of $2^2$ in each of the factorials. We know there is one factor of $2^2$ each in $4!$, $5!$, $6!$, and $7!$, two in $8!$, $9!$, $10$, and $11!$, and so on until we have $4$ factors of $2^1$ in $16!$. Adding them all up, we have $1+1+1+1+2+2+2+2+3+3+3+3+4=28$.

Now we count factors of $2^3$ in each of the factorials. Using a similar method as above, we have a sum of $1+1+1+1+1+1+1+1+2=10$.

Now we count factors of $2^4$ in each of the factorials. Using a similar method as above, we have a factor of $2^4$ in $16$, so there is $1$ factor of $2^4$.

Adding all the factors of $2$, we have $103$. Since $103$ is odd, $m$ has one factor of $2$.

Case 2: Factors of $3$

We use a similar method as in case 1. We first count factors of $3^1$. We obtain the sum $1+1+1+2+2+2+...4+4+4+5+5=50$.

We count factors of $3^2$. We obtain the sum $1+1+1+1+1+1+1+1=8$.

Adding all the factors of $3$, we have $58$. Since $58$ is even, $m$ has $0$ factors of $3$.

Case 3: Factors of $5$

We count the factors of $5^1$: $1+1+1+1+1+2+2+2+2+2+3+3=21$. Since $21$ is odd, $m$ has one factor of $5$.

Case 4: Factors of $7$

We count the factors of $7^1$: $1+1+1+1+1+1+1+2+2+2=13$. Since $13$ is odd, $m$ has one factor of $7$.

Case 5: Factors of $11$

We count the factors of $11^1$: $1+1+1+1+1+1=6$. Since $6$ is even, $m$ has $0$ factors of $11$.

Case 6: Factors of $13$

We count the factors of $13^1$: $1+1+1+1=4$. Since $4$ is even, $m$ has $0$ factors of $13$.

Multiplying out all our factors for $m$, we obtain $2\cdot5\cdot7=\boxed{\text{ (C) }70}$.

~arjken

Solution 7 (Answer Choices)

We see that all the answer choices are divisible by $10$ except for $1001$, and we also notice that the answer choices have $3$, $7$, $11$, or $13$ as a prime factor.

Testing, we see that $3$, $11$, $13$ have an even power in the product, so we have that all the other answer choices will not work.

Therefore we just have $\boxed{\text{ (C) }70}$.

Solution 8 (Fastest Intuition)

Notice that you can add the factor $1!$ to the expression to make it $m\cdot1!\cdot2!\cdot3!\cdot4!\cdot5!\cdot6!\cdot7!\cdot8!\cdot9!\cdot10!\cdot11!\cdot12!\cdot13!\cdot14!\cdot15!\cdot16!$

Every consecutive pair $n!\cdot(n+1)!$ can be simplified to $n+1$ (divide out $n!^2$).

Resulting is the product $m\cdot2\cdot4\cdot6\cdot8\cdot10\cdot12\cdot14\cdot16 = m\cdot2^8\cdot8!$

This is easily simplified to $m\cdot2\cdot5\cdot7 = m\cdot70$ when dividing out perfect squares.

This means that $m$ must have a minimum factor of $70$ which gives answer choice $\boxed{\text{ (C) }70}$.

~coolishu

Solution 9(Pretty Quick similar to solution 8)

$16!\left(15!\right)$ this can be written as $16\left(15!\right)\left(15!\right)$


Thus


$16\left(15!\right)^{2}$

Now lets try

$16!15!14!$

$16\left(15\right)\left(14!\right)15\left(14!\right)\left(14!\right)$


thus $16\left(15\right)^{2}\left(14\right)^{3}$


we can continue this pattern until one to get $m\cdot2!\cdot3!\cdot4!\cdot5!...16! = 16\left(15\right)^{2}\left(14\right)^{3}\left(13\right)^{4}\left(12\right)^{5}\left(11\right)^{6}....\left(1\right)^{15}$

we can remove all the even powers of expression above to get

$16\left(14\right)^{3}\left(12\right)^{5}\left(10\right)^{7}\left(8\right)^{9}\left(6\right)^{11}\left(4\right)^{13}\left(2\right)^{15}$


we can see that all off the numbers are even and multiples of 2,3,5,7

the biggest possible number we should get is 2 times 3 times 5 times 7 which is 210 which means out anwer should be A or C 30 or 70.

Then look all the stuff with 7 which would only consist of ${14}^3$

which needs an extra 7 to give it company, so put answer must be divisble by 7 and less than 210

which leaves 70 or C as our answer

$\boxed{\text{ (C) }70}$.

Note: you can also just remove all pairs of two to get $16\left(14\right)\left(12\right)\left(10\right)\left(8\right)\left(6\right)\left(4\right)\left(2\right)$

Solution 10 (Braindead solution)

List out 1 to 16:

\[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16.\]

First, we remove all numbers that appear an even amount of times in the product:

\[2, 4, 6, 8, 10, 12, 14, 16.\]

Next, we remove all perfect squares:

\[2, 6, 8, 10, 12, 14.\]

Factoring each term gives:

\[2^1, 2^1\cdot 3^1, 2^3, 2^1 \cdot 5^1, 2^2 \cdot 3^1, 2^1 \cdot 7^1.\]

We multiply all the terms together and remove perfect squares to get $2^1 \cdot 5^1 \cdot 7^1 = \boxed{\text{ (C) }70}$.

Solution 11

Note that all prime factors must have an even exponent, and that m must be the multiplied equivalent of all odd-exponent prime factors. The only prime numbers appearing are 2, 3, 5, 7, 11, and 13. We can quickly rule out 11 and 13 since they appear 6 and 4 times, respectively. That leaves 2, 3, 5, and 7. We can see that 2 numbers are multiples: 30 and 70. 30 is 2*5*3, 70 is 2*5*7. If we double-check, 3 comes up an even number of times, so our answer is 70. If there is no time left, this method quickly eliminates enough solutions so that guessing could be preferable to leaving it blank.

~Bjartskular457

~Zzzzzzzzzzzzz

Video Solution 2 by OmegaLearn

https://youtu.be/fB81j1vbwdM

Video Solution 3 by SpreadTheMathLove

https://www.youtube.com/watch?v=sqVY5-h4vfo

Video Solution 4 by paixiao

https://www.youtube.com/watch?v=EvA2Nlb7gi4&t=238s This video link is invalid now.

Video Solution

https://youtu.be/eW9eBpalm7I

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Video Solution by MegaMath

https://www.youtube.com/watch?v=le0KSx3Cy-gt=28s

See also

2023 AMC 10B (Problems • Answer Key • Resources)
Preceded by
Problem 14 		Followed by
Problem 16
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

These problems are copyrighted © by the Mathematical Association of America.

Retrieved from "https://wiki.aopstest.com/wiki/index.php?title=2023_AMC_10B_Problems/Problem_15&oldid=268547"