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"

(proof reading. :))
m
 
(6 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
 +
(''Ricky Liu'') 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 + \cdots + a_k = a_1\cdot a_2\cdots a_k = n</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>.
+
== Solutions ==
  
−
== Solution ==
+
=== Solution 1 ===
−
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:
+
First, consider composite numbers.  We can then factor <math>n</math> into <math>p_1p_2.</math> It is easy to see that <math>p_1+p_2\le n</math>, and thus, we can add <math>(n-p_1-p_2)</math> 1s in order to achieve a sum and product of <math>n</math>.  For <math>p_1+p_2=n</math>, which is only possible in one case, <math>n=4</math>, we consider <math>p_1=p_2=2</math>.
  
 +
Secondly, let <math>n</math> be a prime.  Then we can find the following procedure: Let <math>a_1=\frac{n}{2}, a_2=4, a_3=\frac{1}{2}</math> and let the rest of the <math>a_k</math> be 1.  The only numbers we now need to check are those such that <math>\frac{n}{2}+4+\frac{1}{2}>n\Longrightarrow n<9</math>.  Thus, we need to check for <math>n=1,2,3,5,7</math>.  One is included because it is neither prime nor composite.
  
 +
For <math>n=1</math>, consider <math>a_1a_2\hdots a_k=1</math>.  Then by AM-GM, <math>a_1+a_2+\hdots+a_k\ge k\sqrt[k]{1}>1</math> for <math>k\ge 2</math>.  Thus, <math>n=1</math> is impossible.
  
−
''Case 1: n is prime''
+
If <math>n=2</math>, once again consider <math>a_1a_2\hdots a_k=2</math>.  Similar to the above, <math>a_1+a_2+\hdots\ge k\sqrt[k]{2}>2</math> for <math>k\ge 2</math> since <math>\sqrt[k]{2}>1</math> and <math>k>2</math>. Obviously, <math>n=2</math> is then impossible.
  
−
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 <math>n=3</math>, let <math>a_1a_2\hdots a_k=3</math>.  Again, <math>a_1+a_2+\hdots\ge k\sqrt[k]{3}>3</math>. This is obvious for <math>k\ge 3</math>. Now consider <math>k=2</math>. Then <math>2\sqrt{3}\approx 3.4</math> is obviously greater than <math>3</math>. Thus, <math>n=3</math> is impossible.
  
 +
If <math>n=5</math>, proceed as above and consider <math>k=2</math>.  Then <math>a_1+a_2=5</math> and <math>a_1a_2=5</math>.  However, we then come to the quadratic <math>a_1^2-5a_1+5=0 \Longrightarrow a_1=\frac{5\pm\sqrt{5}}{2}</math>, which is not rational.  For <math>k=3</math> and <math>k=4</math> we note that <math>\sqrt[3]{5}>\frac{5}{3}</math> and <math>\sqrt[4]{5}>\frac{5}{4}</math>.  This is trivial to prove.  If <math>k\ge 5</math>, it is obviously impossible, and thus <math>n=5</math> does not work.
  
 +
The last case, where <math>n=7</math>, is possible using the following three numbers.  <math>a_1=\frac{9}{2}, a_2=\frac{4}{3}, a_3=\frac{7}{6}</math> shows that <math>n=7</math> is possible.
  
−
''Case 2: n is composite''
+
Hence, <math>n</math> can be any positive integer greater than <math>3</math> with the exclusion of <math>5</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>:
+
{{alternate solutions}}
  
−
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>.
+
== See also ==
 +
* <url>viewtopic.php?t=84554 Discussion on AoPS/MathLinks</url>
  
−
[[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.
+
{{USAMO newbox|year=2006|num-b=3|num-a=5}}
−
 
 
−
 
 
−
 
 
−
''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 ==
 
−
 
 
−
* [[2006 USAMO Problems]]
 
−
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=490647#p490647 Discussion on AoPS/MathLinks]
 
  
 
[[Category:Olympiad Number Theory Problems]]
 
[[Category:Olympiad Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 21:43, 5 August 2014

Problem

(Ricky Liu) 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 + \cdots + a_k = a_1\cdot a_2\cdots a_k = n$.

Solutions

Solution 1

First, consider composite numbers. We can then factor $n$ into $p_1p_2.$ It is easy to see that $p_1+p_2\le n$, and thus, we can add $(n-p_1-p_2)$ 1s in order to achieve a sum and product of $n$. For $p_1+p_2=n$, which is only possible in one case, $n=4$, we consider $p_1=p_2=2$.

Secondly, let $n$ be a prime. Then we can find the following procedure: Let $a_1=\frac{n}{2}, a_2=4, a_3=\frac{1}{2}$ and let the rest of the $a_k$ be 1. The only numbers we now need to check are those such that $\frac{n}{2}+4+\frac{1}{2}>n\Longrightarrow n<9$. Thus, we need to check for $n=1,2,3,5,7$. One is included because it is neither prime nor composite.

For $n=1$, consider $a_1a_2\hdots a_k=1$. Then by AM-GM, $a_1+a_2+\hdots+a_k\ge k\sqrt[k]{1}>1$ for $k\ge 2$. Thus, $n=1$ is impossible.

If $n=2$, once again consider $a_1a_2\hdots a_k=2$. Similar to the above, $a_1+a_2+\hdots\ge k\sqrt[k]{2}>2$ for $k\ge 2$ since $\sqrt[k]{2}>1$ and $k>2$. Obviously, $n=2$ is then impossible.

If $n=3$, let $a_1a_2\hdots a_k=3$. Again, $a_1+a_2+\hdots\ge k\sqrt[k]{3}>3$. This is obvious for $k\ge 3$. Now consider $k=2$. Then $2\sqrt{3}\approx 3.4$ is obviously greater than $3$. Thus, $n=3$ is impossible.

If $n=5$, proceed as above and consider $k=2$. Then $a_1+a_2=5$ and $a_1a_2=5$. However, we then come to the quadratic $a_1^2-5a_1+5=0 \Longrightarrow a_1=\frac{5\pm\sqrt{5}}{2}$, which is not rational. For $k=3$ and $k=4$ we note that $\sqrt[3]{5}>\frac{5}{3}$ and $\sqrt[4]{5}>\frac{5}{4}$. This is trivial to prove. If $k\ge 5$, it is obviously impossible, and thus $n=5$ does not work.

The last case, where $n=7$, is possible using the following three numbers. $a_1=\frac{9}{2}, a_2=\frac{4}{3}, a_3=\frac{7}{6}$ shows that $n=7$ is possible.

Hence, $n$ can be any positive integer greater than $3$ with the exclusion of $5$.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See also

  • <url>viewtopic.php?t=84554 Discussion on AoPS/MathLinks</url>
2006 USAMO (Problems • Resources)
Preceded by
Problem 3 		Followed by
Problem 5
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

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