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)
(making it shorter)
Line 4: Line 4:
  
 
== 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:
+
Let polynomial <math>P(x)</math> be a [[monic polynomial]] such that it's roots are only all of <math>a_1</math> through <math>a_k</math>. 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:
  
  

Revision as of 11:06, 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 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$. 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=22848"