2006 USAMO Problems/Problem 4

Problem

Find all positive integers $n$ such that there are $k\ge 2$ positive rational numbers $a_1,a_2,\ldots a_k$ satisfying $a_1+a_2+...+a_k = a_1 \cdot a_2 \cdot \cdots a_k = n$ .

Solution

Let polynomial $P(x)$ be a monic polynomial such that it's roots are only all of $a_1$ through $a_k$ . Therefore, the sum and product of the roots is n, and the constant term of $P(x)$ is $\pm n$ . From the Rational Root Theorem, all $a_i$ are divisors of n, and integral. We split this into cases:

Case 1: n is prime

If n is prime, the only divisors of n are 1 and n. We must have an n in $a_i$ so that $a_1 \cdot a_2 \cdot \cdots a_k = n$ , but then $a_1+a_2+...+a_k>n$ , since $k\geq 1$ . We have a contradiction, therefore n may not be prime.

Case 2: n is composite

Let two divisors of n(not necessarily distinct) be $d_1$ and $d_2$ , such that $d_1\cdot d_2 = n$ and $d_1,d_2<n$ . We will prove that $d_1+d_2 \leq n$ :

We subtract $d_1+d_2$ from $d_1d_2$ : $d_1d_2-d_1-d_2$ . Now we add 1: $d_1d_2-d_1-d_2+1=(d_1-1)(d_2-1)$ . Since $d_1$ and $d_2$ are greater than 1, $d_1 -1$ and $d_2 -1$ are positive. Therefore, $d_1d_2\geq d_1+d_2$ , and $d_1+d_2\leq n$ .

WLOG, we let $a_1=d_1$ and $a_2=d_2$ . If $n-a_1-a_2>0$ , we can let the rest of the numbers be ones. Therefore, there are such k when n is composite.

Case 3: n=1

Therefore, k=1, but $k\geq 2$ , so that is impossible.

Therefore, there are such $k\geq 2$ such that $a_1+a_2+...+a_k = a_1 \cdot a_2 \cdot \cdots a_k = n$ only when n is composite.

Page

Toolbox

Search

2006 USAMO Problems/Problem 4

Problem

Solution

See Also