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"

(found a mistake, fixed it.)
(→‎Solution)
Line 18: Line 18:
 
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> and <math>d_1,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> and <math>d_1,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_1d_2\geq d_1+d_2</math>, and <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 greater than 1, <math>d_1 -1</math> and <math>d_2 -1</math> are positive. Therefore, <math>d_1d_2\geq d_1+d_2</math>, and <math>d_1+d_2\leq n</math>.
  
 
[[WLOG]], we let <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.
 
[[WLOG]], we let <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.

Revision as of 11:09, 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$ 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.

See Also

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