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 "2023 AMC 10B Problems/Problem 15"

(→‎Solution 1)
Line 45: Line 45:
  
 
~yourmomisalosinggame (a.k.a. Aaron) & ~Technodoggo (add more examples)
 
~yourmomisalosinggame (a.k.a. Aaron) & ~Technodoggo (add more examples)
 +
 +
== Solution 4 (Bashy method) ==
 +
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.
 +
 +
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>.
 +
 +
Case 1: Factors of <math>2</math>
 +
 +
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>.
 +
 +
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 <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 <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>.
 +
 +
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>.
 +
 +
Case 2: Factors of <math>3</math>
 +
 +
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 count factors of <math>3^2</math>. We obtain the sum <math>1+1+1+1+1+1+1+1=8</math>.
 +
 +
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>.
 +
 +
Case 3: Factors of <math>5</math>
 +
 +
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>.
 +
 +
Case 4: Factors of <math>7</math>
 +
 +
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>.
 +
 +
Case 5: Factors of <math>11</math>
 +
 +
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>.
 +
 +
Case 6: Factors of <math>13</math>
 +
 +
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>.
 +
 +
Multiplying out all our factors for <math>m</math>, we obtain <math>2\cdot\cdot5\cdot7=\boxed{\text{ (C) }70}</math>.

Revision as of 17:41, 15 November 2023

Problem

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

Solution 1

Consider 2, there are odd number of 2's in $2!\cdot3!\cdot4!\cdot5!...16!$ (We're not counting 3 2's in 8, 2 3's in 9, etc).

There are even number of 3's in $2!\cdot3!\cdot4!\cdot5!...16!$ ...etc,


So, we original expression reduce to \begin{align*} m \cdot 2 \cdot 4 \cdot 6 \cdot 8 \cdot 10 \cdot 12 \cdot 14 \cdot 16 &\equiv m \cdot 2^8 \cdot (1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8)\\ &\equiv m \cdot 2 \cdot 3 \cdot (2 \cdot 2) \cdot 5 \cdot (2 \cdot 3) \cdot 7 \cdot (2 \cdot 2 \cdot 2)\\ &\equiv m \cdot 2 \cdot 5 \cdot 7\\ m &= 2 \cdot 5 \cdot 7 = 70 \end{align*}

~Technodoggo

Solution 2

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 $7!$ 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 $7!$ to $16!$, 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 3

First, we note $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}$.

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

Solution 4 (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\cdot\cdot5\cdot7=\boxed{\text{ (C) }70}$.

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