2023 AMC 10B Problem 15

P11-15~5 minPrint

Number Properties Divisibility & Factors Primes Apply an identity: SFFT, sum of squares, difference of cubes, Vieta Use an invariant, parity, or coloring argument

What is the least positive integer $m$ such that $m \cdot 2! \cdot 3!\cdot 4!\cdot 5! \dots 16!$ is a perfect square?

Show solution without answering

Key insight

Pair each factorial with the next, like 3! times 4! = (3!) squared times 4. What remains is a square times 8!, and 8! needs 2 times 5 times 7.

Solution

A number is a perfect square when every prime in it appears an even number of times. The product of sixteen factorials is enormous, so first pull out as big a square as possible.

1. Add $1!$ . Since $1! = 1$ , the product is $1! \cdot 2! \cdot 3! \cdots 16!$ . Now there are $16$ factorials, and we can pair them up: $(1!, 2!)$ , $(3!, 4!)$ , $\ldots$ , $(15!, 16!)$ .
2. Look at one pair. $4! = 4 \times 3!$ , so
$3! \cdot 4! = 3! \cdot 3! \cdot 4 = (3!)^2 \cdot 4.$
The same happens for every pair: an odd factorial times the next one is (odd factorial) squared times the next even number. For example, $5! \cdot 6! = (5!)^2 \cdot 6$ .
3. Collect the leftovers. Every pair gives a square times one even number. The even numbers left over are
$2 \cdot 4 \cdot 6 \cdot 8 \cdot 10 \cdot 12 \cdot 14 \cdot 16.$
4. Simplify the leftovers. Take a $2$ out of each of the eight numbers:
$2 \cdot 4 \cdot 6 \cdots 16 = 2^8 \cdot (1 \cdot 2 \cdot 3 \cdots 8) = 2^8 \cdot 8!.$
$2^8 = (2^4)^2$ is already a square. So the whole product is a square times $8!$ .
5. Factor $8!$ .
$8! = 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 = 2^7 \cdot 3^2 \cdot 5 \cdot 7.$
The primes that appear an odd number of times are $2$ (seven times), $5$ (once) and $7$ (once).
6. Fix them. Multiplying by one more $2$ , one more $5$ and one more $7$ makes every count even, and nothing smaller does:
$m = 2 \cdot 5 \cdot 7 = 70.$

The answer is $\boxed{\textbf{(C)}\ 70}$ .

Why this works

To make a product into a perfect square with the smallest multiplier, multiply by each prime that appears an odd number of times, once. The pairing trick avoids counting primes across sixteen factorials: it pulls out a huge square in one step and leaves one small number, $8!$ , to factor.

Alternative approach

Use the answer choices and count a few primes.

The prime $11$ . It is a factor of $11!, 12!, \ldots, 16!$ , once in each: $6$ times in all. Six is even, so $m$ should not contain $11$ .
The prime $13$ . It is in $13!, 14!, 15!, 16!$ : $4$ times, also even. So $m$ should not contain $13$ either. That rules out $30030$ , $1430$ and $1001$ , which all contain $11$ or $13$ .
The prime $7$ . It appears once in each of $7!, 8!, \ldots, 13!$ ( $7$ factorials) and twice in each of $14!, 15!, 16!$ , because $14 = 2 \cdot 7$ brings a second $7$ . That is $7 + 6 = 13$ times, which is odd. So $m$ must contain $7$ , and of $30$ and $70$ only $70$ does.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Since $1! = 1$ , the product equals $1! \cdot 2! \cdots 16!$ . Group the factorials in consecutive pairs and use $(2k)! = 2k \cdot (2k-1)!$ :
$(2k-1)! \cdot (2k)! = \big((2k-1)!\big)^2 \cdot 2k.$
Doing this for $k = 1, \dots, 8$ ,
$\prod_{j=1}^{16} j! = \Big(\prod_{k=1}^{8} (2k-1)!\Big)^2 \cdot (2 \cdot 4 \cdot 6 \cdots 16) = (\text{square}) \cdot 2^8 \cdot 8!.$
The factor $2^8$ is a square, so everything hinges on $8! = 40320 = 2^7 \cdot 3^2 \cdot 5 \cdot 7$ . The primes with odd exponent are $2$ , $5$ and $7$ , so the smallest $m$ that makes the whole product a square is
$m = 2 \cdot 5 \cdot 7 = 70.$

The answer is $\boxed{\textbf{(C)}\ 70}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 1: Integers: The Basics
Introduction to Number Theory, Chapter 2: Primes and Composites
Introduction to Algebra, Chapter 11: Special Factorizations
Introduction to Algebra, Chapter 20: Special Functions (§20.3)