2013 AMC 10B Problem 20

P16-20~6 minPrint

Primes Divisibility & Factors Bound the quantity above/below or estimate to pin it down Consider the largest/smallest element or boundary case

The number $2013$ is expressed in the form $2013=\frac{a_1!a_2!\cdots a_m!}{b_1!b_2!\cdots b_n!},$ where $a_1\ge a_2\ge\cdots\ge a_m$ and $b_1\ge b_2\ge\cdots\ge b_n$ are positive integers and $a_1+b_1$ is as small as possible. What is $|a_1-b_1|$ ?

Show solution without answering

Key insight

2013 has the prime factor 61, so the top needs 61!. That brings in the prime 59, so the bottom needs 59! to cancel it.

Solution

This asks for the smallest possible $a_1 + b_1$ , so there are two halves: show it cannot be smaller than some value, then show that value can be reached.

Break $2013$ into primes: $2013 = 3 \times 11 \times 61$ , and $61$ is prime.

Part 1: $a_1 + b_1$ is at least $120$ .

The biggest prime is the hardest to produce, so look at it first. The factorial $k! = 1 \times 2 \times \cdots \times k$ contains the prime $61$ only if $k \ge 61$ . The $61$ in $2013$ must come from the top, so the largest top factorial satisfies $a_1 \ge 61$ .
But $61!$ also contains the prime $59$ , and $59$ does not divide $2013$ . So some factorial on the bottom must cancel it, and only a factorial of $59$ or more contains $59$ . So $b_1 \ge 59$ .
Together, $a_1 + b_1 \ge 61 + 59 = 120$ . The only way to reach exactly $120$ is $a_1 = 61$ and $b_1 = 59$ .

Part 2: $120$ can be reached.

5. Start with $\frac{61!}{59!} = 61 \times 60 = 3660$ . Compare it with $2013 = 61 \times 33$ :
$\frac{3660}{2013} = \frac{61 \times 60}{61 \times 33} = \frac{60}{33} = \frac{20}{11}.$
So we still need to divide by $20$ and multiply by $11$ .
6. Small factorials can do both: $\frac{19!}{20!} = \frac{1}{20}$ and $\frac{11!}{10!} = 11$ . So
$2013 = \frac{61! \cdot 19! \cdot 11!}{59! \cdot 20! \cdot 10!}.$
Check: $3660 \div 20 = 183$ and $183 \times 11 = 2013$ . The top numbers $61, 19, 11$ and the bottom numbers $59, 20, 10$ are each in decreasing order, as required.
7. So $a_1 = 61$ , $b_1 = 59$ , and $|a_1 - b_1| = 2$ .

The answer is $\boxed{\textbf{(B)}\ 2}$ .

Why this works

A fraction of factorials is a product of runs of whole numbers, so the largest prime in the target decides how big the top factorial must be. Any unwanted prime just below it then has to be cancelled by a bottom factorial almost as big. Prove the limit using the biggest prime and the next prime down, then build an example that reaches it.

Concise solution

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

Factor: $2013 = 3 \cdot 11 \cdot 61$ .

Lower bound. The prime $61$ must divide the numerator, and $61 \mid k!$ only when $k \ge 61$ , so $a_1 \ge 61$ . But then $a_1!$ is divisible by the prime $59$ (and by $53, 47, \dots$ ), which does not divide $2013$ , so $59$ must be cancelled by the denominator: some $b_j!$ is divisible by $59$ , forcing $b_1 \ge 59$ . Hence $a_1 + b_1 \ge 61 + 59 = 120$ .

Construction. Try $a_1 = 61$ , $b_1 = 59$ : $\frac{61!}{59!} = 61 \cdot 60 = 3660$ , and $\frac{3660}{2013} = \frac{60}{33} = \frac{20}{11}$ . We still need to divide by $20$ and multiply by $11$ , which factorials do easily:
$2013 = \frac{61! \cdot 19! \cdot 11!}{59! \cdot 20! \cdot 10!},$
since $\frac{19!}{20!} = \frac{1}{20}$ and $\frac{11!}{10!} = 11$ . The ordering conditions hold, and $a_1 + b_1 = 120$ is minimal.

Therefore $|a_1 - b_1| = 61 - 59 = 2$ .

The answer is $\boxed{\textbf{(B)}\ 2}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 2: Primes and Composites
Introduction to Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
Introduction to Number Theory, Chapter 4: Prime Factorization (§4.2, §4.4)
Introduction to Number Theory, Chapter 5: Divisor Problems (§5.2, §5.3)