Difference between revisions of "2006 USAMO Problems/Problem 4"
(Standardized) |
(Could someone check this please?) |
||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| − | Find all positive integers <math> | + | Find all positive integers <math>n</math> such that there are <math>k\ge 2</math> positive rational numbers <math>a_1,a_2,\ldots a_k</math> satisfying <math>a_1+a_2+...+a_k = a_1 \cdot a_2 \cdot \cdots a_k = n</math>. |
== Solution == | == Solution == | ||
| + | Let polynomial <math>P(x)</math> be such that it's roots are only all of <math>a_1</math> through <math>a_k</math>, and let the coefficient of <math>x^k</math> be 1. Therefore, the sum and product of the roots is n, and the constant term of <math>P(x)</math> is <math>\pm n</math>. From the [[Rational Root Theorem]], all <math>a_i</math> 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 <math>a_i</math> so that <math>a_1 \cdot a_2 \cdot \cdots a_k = n</math>, but then <math>a_1+a_2+...+a_k>n</math>, since <math>k\geq 1</math>. We have a contradiction, therefore n may not be prime. | ||
| + | |||
| + | |||
| + | |||
| + | ''Case 2: n is composite'' | ||
| + | Let two divisors of n(not necessarily distinct) be <math>d_1</math> and <math>d_2</math>, such that <math>d_1\cdot d_2 = n</math>. We will prove that <math>d_1+d_2 \leq n</math>: | ||
| + | |||
| + | We subtract <math>d_1+d_2</math> from <math>d_1d_2</math>: <math>d_1d_2-d_1-d_2</math>. Now we add 1: <math>d_1d_2-d_1-d_2+1=(d_1-1)(d_2-1)</math>. Since <math>d_1</math> and <math>d_2</math> are positive, <math>d_1 -1</math> and <math>d_2 -1</math> are nonnegative. Therefore, <math>d_1+d_2\leq n</math>. | ||
| + | |||
| + | We let, [[WLOG]], <math>a_1=d_1</math> and <math>a_2=d_2</math>. If <math>n-a_1-a_2>0</math>, 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 <math>k\geq 2</math>, so that is impossible. | ||
| + | |||
| + | |||
| + | |||
| + | Therefore, there are such <math>k\geq 2</math> such that <math>a_1+a_2+...+a_k = a_1 \cdot a_2 \cdot \cdots a_k = n</math> only when n is composite. | ||
== See Also == | == See Also == | ||
Revision as of 12:04, 28 January 2008
Problem
Find all positive integers 
such that there are 
positive rational numbers 
satisfying 
.
Solution
Let polynomial 
be such that it's roots are only all of 
through 
, and let the coefficient of 
be 1. Therefore, the sum and product of the roots is n, and the constant term of is 
. From the Rational Root Theorem, all 
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 so that 
, but then 
, since 
. We have a contradiction, therefore n may not be prime.
Case 2: n is composite
Let two divisors of n(not necessarily distinct) be 
and 
, such that 
. We will prove that 
:
We subtract 
from 
: 
. Now we add 1: 
. Since and are positive, 
and 
are nonnegative. Therefore, 
.
We let, WLOG, 
and 
. If 
, 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 
, so that is impossible.
Therefore, there are such such that only when n is composite.
