Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2006 USAMO Problems/Problem 4"

(→‎Solution)
(→‎Solution)
Line 9: Line 9:
  
 
''Case 1: n is prime''
 
''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.
 
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.
  
Line 14: Line 15:
  
 
''Case 2: n is composite''
 
''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>:
 
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>:
  
Line 23: Line 25:
  
 
''Case 3: n=1''
 
''Case 3: n=1''
 +
 
Therefore, k=1, but <math>k\geq 2</math>, so that is impossible.
 
Therefore, k=1, but <math>k\geq 2</math>, so that is impossible.
  

Revision as of 11:05, 28 January 2008

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 such that it's roots are only all of $a_1$ through $a_k$, and let the coefficient of $x^k$ be 1. 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$. 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 positive, $d_1 -1$ and $d_2 -1$ are nonnegative. Therefore, $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.

See Also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_USAMO_Problems/Problem_4&oldid=22847"