2000 AMC 10 Problem 1

P1-10~1 minPrint

Divisibility & Factors Primes Set up the equation/formula and compute; no special trick needed Consider the largest/smallest element or boundary case

In the year $2001$ , the United States will host the International Mathematical Olympiad. Let $I,M,$ and $O$ be distinct positive integers such that the product $I \cdot M \cdot O = 2001$ . What is the largest possible value of the sum $I + M + O$ ?

Show solution without answering

Key insight

Break 2001 into primes: 3, 23 and 29. To make the sum big, make two of the numbers as small as possible, 1 and 3.

Solution

1. First break $2001$ into primes. Its digits add to $2 + 0 + 0 + 1 = 3$ , so $3$ divides it: $2001 = 3 \cdot 667$ . Trying small primes on $667$ gives $667 = 23 \cdot 29$ . So
$2001 = 3 \cdot 23 \cdot 29.$
2. Now think about what makes a sum big when the product is fixed. Compare $36 = 6 \cdot 6$ (sum $12$ ) with $36 = 1 \cdot 36$ (sum $37$ ). Lopsided numbers give a much bigger sum. So we want two tiny numbers and one huge one.
3. The three numbers must be different positive whole numbers. The smallest one we can use is $1$ . The next smallest number that divides $2001$ is $3$ . That leaves $2001 \div 3 = 667$ for the third number.
4. The sum is $1 + 3 + 667 = 671$ .
5. To be safe, list every other way to write $2001$ as a product of three different numbers:

numbers	sum
$1, 3, 667$	$671$
$1, 23, 87$	$111$
$1, 29, 69$	$99$
$3, 23, 29$	$55$

The first row is the largest.

The answer is $\boxed{\textbf{(E)}\ 671}$ .

Why this works

When the product of some numbers is fixed, their sum gets bigger as the numbers get more spread out. So the best choice uses the smallest possible numbers, and $1$ counts. The word "different" only stops you from using $1, 1, 2001$ .

Alternative approach

Use the answer choices. Once you see $2001 = 3 \cdot 667$ , the numbers $1, 3, 667$ are allowed and add to $671$ . That is the biggest choice offered, and it can actually be reached, so it must be the answer.

Concise solution

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

The digit sum of $2001$ is $3$ , so $3$ divides it: $2001 = 3 \cdot 667 = 3 \cdot 23 \cdot 29$ .

We want three distinct positive integers whose product is $2001$ and whose sum is as large as possible. For a fixed product, a sum grows as the factors become more lopsided, so we want one giant factor and two tiny ones. The two smallest distinct factors we can use are $1$ and $3$ , which leaves $667$ for the third:
$1 + 3 + 667 = 671.$

For comparison, the other ways to split $2001$ into three distinct factors give $1 + 23 + 87 = 111$ , $1 + 29 + 69 = 99$ , and $3 + 23 + 29 = 55$ , all smaller.

The answer is $\boxed{\textbf{(E)}\ 671}$ .

Review in the AoPS books

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