Difference between revisions of "2006 USAMO Problems/Problem 4"
Mathcrazed (talk | contribs) (→Solution) |
5849206328x (talk | contribs) m |
||
(One intermediate revision by one other user 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>. | ||
− | + | == Solutions == | |
− | == Solution == | + | === Solution 1 === |
− | + | 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>. | |
− | First, consider composite numbers. We can then factor <math>n</math> into <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. | 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. | ||
Line 13: | Line 13: | ||
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 <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 <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 | + | 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. | 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. | ||
Line 21: | Line 21: | ||
Hence, <math>n</math> can be any positive integer greater than <math>3</math> with the exclusion of <math>5</math>. | Hence, <math>n</math> can be any positive integer greater than <math>3</math> with the exclusion of <math>5</math>. | ||
− | == See | + | {{alternate solutions}} |
+ | |||
+ | == See also == | ||
+ | * <url>viewtopic.php?t=84554 Discussion on AoPS/MathLinks</url> | ||
− | + | {{USAMO newbox|year=2006|num-b=3|num-a=5}} | |
− | |||
[[Category:Olympiad Number Theory Problems]] | [[Category:Olympiad Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 22:43, 5 August 2014
Contents
Problem
(Ricky Liu) Find all positive integers such that there are
positive rational numbers
satisfying
.
Solutions
Solution 1
First, consider composite numbers. We can then factor into
It is easy to see that
, and thus, we can add
1s in order to achieve a sum and product of
. For
, which is only possible in one case,
, we consider
.
Secondly, let be a prime. Then we can find the following procedure: Let
and let the rest of the
be 1. The only numbers we now need to check are those such that
. Thus, we need to check for
. One is included because it is neither prime nor composite.
For , consider
. Then by AM-GM,
for
. Thus,
is impossible.
If , once again consider
. Similar to the above,
for
since
and
. Obviously,
is then impossible.
If , let
. Again,
. This is obvious for
. Now consider
. Then
is obviously greater than
. Thus,
is impossible.
If , proceed as above and consider
. Then
and
. However, we then come to the quadratic
, which is not rational. For
and
we note that
and
. This is trivial to prove. If
, it is obviously impossible, and thus
does not work.
The last case, where , is possible using the following three numbers.
shows that
is possible.
Hence, can be any positive integer greater than
with the exclusion of
.
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.