Find all positive integers $n$ such that there are $k \geq 2$ positive rational numbers $a_1, a_2, \ldots, a_k$ satisfying $a_1 + a_2 + \ldots + a_k = a_1 \cdot a_2 \cdots a_k = n.$
Problem
Source: USAMO 2006, Problem 4, proposed by Ricky Liu
Tags: AMC, USA(J)MO, USAMO, quadratics, algebra unsolved, algebra
20.04.2006 22:52
Eh...
20.04.2006 23:06
14.04.2008 07:15
How did you people figure out the solution to 7?
06.09.2008 22:49
Sorry, but can somebody answer Differ's question? I have the same question.
22.09.2008 02:20
? [10 chars]
22.09.2008 02:30
Differ wrote: How did you people figure out the solution to 7? I guess the motivation is as follows. Proving that 2, 3, 5 don't work isn't too bad, and you'll (obviously) notice that the proof doesn't work for 7. It would seem that you need something pretty contrived or powerful in order to prove that stuff doesn't work in a different way, but this is #4. Always remember that #1's and #4's for the most part have solutions that don't involve anything particularly tricky if you think in the right general direction for long enough. Also, they won't use big theorems or ideas. So assume that there's some easy thing to do. Maybe it's one of those annoying problems where the answer is "yes, it exists." This should at least cross your mind. Anyway, you first try k=2. It's easy to see by solving the quadratic with that you get irrational numbers. If you play around with k=3, you'll eventually be led to the solution...I guess the key word is play, keep experimenting. As said before, being #4, the answer probably won't be something ridiculous like a_1 = 3912/37, a_2 = 3010395/1337, whatever.
06.04.2009 05:31
I did n=1,2,3,5 similar to chess64 with AM-GM, then found the same case for n=7. But instead of splitting the rest by composite and prime, I did even and odd: For $ n=2m$, consider the numbers $ 2,m,1,1,1,...$. For $ n$ odd, consider $ \frac{n}{2},4,\frac{1}{2},1,1,...$ The first case works when $ 2+m\leq 2m \iff m\geq 2 \iff n\geq 4$, the second when $ \frac{n}{2}+4+\frac{1}{2} \leq n \iff n\geq 9$. Finding the case for $ n=7$ was particularly unhappy for me. I easily limited it down to $ k=3,4$ by AM-GM arguments and excluding $ k=2$. Then I tried $ k=3$, attempting to solve $ a+b+c=abc=7$. I ended up with an argument like this: for fixed $ a$, we have the equations $ b+c=7-a, bc=\frac{7}{a}$. Then, $ b,c,$ are roots of the quadratic $ x^2-(7-a)x+\frac{7}{a}$, with discriminant $ a^2-14a+49-\frac{28}{a}$ necessarily a perfect square of a rational. Then, knowing there had to be at least one fraction with 7 (or a multiple of 7) in the numerator, I tried $ a=\frac{7}{i}$ for $ i=2,3,4,5,6$ until I hit the jackpot with 7/6.
08.03.2014 00:45
Another construction for the case $n=7$ is $\frac 76 + \frac 43 + \frac 32 + 3 = 7$. Indeed it's a matter of trying things until you get something that works, since it seems pretty hard for a #4 to try and prove that $7$ is not constructible.
22.03.2020 06:17
All $n$ except for $1$, $2$, $3$, $5$ work. For composite $n=xy$, since $x+y\le xy$, we can take $x+y+1+\cdots+1=xy\cdot 1\cdots 1=n$. For prime $n\ge 11$, we can take \[\frac n2+\frac12+4+1+\cdots+1=n\]since $\frac{n+1}{2}+4\le n$. For $n=7$, we have \[\frac76+\frac92+\frac43=\frac76\cdot\frac92\cdot\frac43=7.\] For $n=1,2,3,5$, we have that \[\frac nk\ge\sqrt[k]n.\]This is clearly not true for $k\ge n$, so we only have to check $k$ such that $2\le k<n$. $n=1,2$. No values of $k$ exist to check. $n=3$. We have $3\ge k\sqrt[k]{3}$, which does not hold for $k=2$. $n=5$. We have $5\ge k\sqrt[k]{5}$, which does not hold for $k=3,4$. For $k=2$, we have \[a_1+a_2=a_1a_2=5,\]but solving gives \[\{a_1,a_2\}=\left\{\frac{5-\sqrt5}{2},\frac{5+\sqrt5}{2}\right\},\]which are irrational.
25.08.2020 03:07
The answer is all positive integers except $1,2,3,5.$ $\textbf{Claim: }$ All odd $n\ge 9$ work. $\emph{Proof: }$ Let $m=\frac{n-9}{2}.$ We have $$\underbrace{1+1+\dots+1}_{m\text{ ones}}+\frac{n}{2}+\frac{1}{2}+4=n,$$$$\underbrace{(1)(1)\dots (1)}_{m\text{ ones}}\left(\frac{n}{2}\right)\left(\frac{1}{2}\right)(4)=n.$$Therefore, $(a_1,a_2,\dots,a_{m+3})=\left(1,1,\dots,1,\frac{n}{2},\frac{1}{2},4\right)$ works, so we are done. $\blacksquare$ $\textbf{Claim: }$ All even $n\ge 4$ work. $\emph{Proof: }$ Let $m=\frac{n-4}{2}.$ We have $$\underbrace{1+1+\dots+1}_{m\text{ ones}}+\frac{n}{2}+2=n,$$$$\underbrace{(1)(1)\dots (1)}_{m\text{ ones}}\left(\frac{n}{2}\right)(2)=n.$$Hence, $(a_1,a_2,\dots,a_{m+2})=(1,1,\dots,1,\frac{n}{2},2)$ works. $\blacksquare$ $\textbf{Claim: }$ $n=7$ works. $\emph{Proof:}$ The triple $(a_1,a_2,a_3)=(\frac{9}{2},\frac{7}{6},\frac{4}{3})$ works. $\blacksquare$ $\textbf{Claim: }$ $n=1,2,3,5$ don't work. $\emph{Proof: }$ Suppose $a_1+a_2+\dots+a_k=a_{1}a_{2}\dots a_{k}=n.$ Then, by AM-GM, $$\frac{n}{k}\ge\sqrt[k]{n}\implies n\ge k^{k/(k-1)}.$$Note that $x^{x/(x-1)}$ increases as $x$ increases. Therefore, since $3^{3/2}>5,$ we must have $k=2.$ But it is easy to check that there are no $a_1,a_2$ such that $a_1+a_2=n$ and $a_{1}a_{2}=n$ for $n=1,2,3,5,$ as desired. $\blacksquare$
14.01.2021 09:38
For even numbers $n\geq 4$, observe that $\frac{n}{2}\cdot 2\cdot \underbrace{1\cdot1\cdots \cdot 1}_{\frac{n}{2}-2}=n=\frac{n}{2}+\underbrace{1+1+\cdots +1}_{\frac{n}{2}-2}+2.$ For odd $n\geq 9, \frac{n}{2}\cdot\frac{1}{2}\cdot 4\cdot\underbrace{1\cdot1\cdots \cdot 1}_{\frac{n-9}{2}}=n=\frac{n}{2}+\frac{1}{2}+4+\underbrace{1+1+\cdots +1}_{\frac{n-9}{2}}.$ For $n=7,$ one can see that $\frac{7}{6}\cdot\frac{4}{3}\cdot\frac{9}{2}=7=\frac{7}{6}+\frac{4}{3}+\frac{9}{2}.$ For $n\in\{1,2,3,5\},$ assume there are $\ell$ positive rationals $\geq 1$ named $G_1,G_2,...,G_{\ell}$ (If there are none then the product is less than $1$) then $\ell < n$ and $G_1+G_2+...+G_{\ell}\geq \ell \sqrt[\ell]{G_1G_2...G_{\ell}}\geq \ell \sqrt[\ell]{n}> n,$ contradiction.
17.02.2021 04:50
s t o r a g e The answer is all $n$ except $1,2,3,5$. First, we note that all composite $n$ work: factor $n$ into $p\cdot q$ for $p,q\geq 2$. Taking $p$, $q$, and $n-p-q$ ones works, since \[n-p-q=pq-p-q=(p-1)(q-1)-1\geq 0\]as $p,q\geq 2$. We also note that all primes $\geq 7$ work. For $7$, simply take the set $\frac{7}{6},\frac{4}{3},\frac{9}{2}$. For all primes $p$ greater than $7$, we can take the construction $\frac{p}{2}$,$\frac{1}{2}$, $4$, and $\frac{p-9}{2}$ ones. Now I'll show that $1,2,3,5$ don't work. Clearly $k=2$ does not yield a valid solution for all four of these numbers. Suppose $k\geq 3$. By AM-GM we have that \[n\geq k\cdot n^{\frac{1}{k}}\]One can show that the right hand side is an increasing function in $k$, and that minimum occurs at $k=\ln n$. Since $\ln n<3$ for $n=1,2,3,5$, it suffices to check that $n\geq 3\cdot n^{\frac{1}{3}}$. However, this is only true when $n\geq 3\sqrt 3$, so there does not exist a valid $k\geq 3$ for $n=1,2,3,5$, and thus they don't work.
30.03.2022 18:15
The answer is all positive integers except for $1,2,3,5$. Case 1: $n<4$ First note that by AM-GM, $\frac nk\ge\sqrt[k]n$, so $n\ge k^{\frac k{k-1}}$. Since $k\ge2$, this implies $n\ge4$. Case 2: $n=5$ Then $k\le2$ from the aforementioned bound, so $k=2$. If we let $a_1+a_2=a_1a_2=5$, then solving we get: $$a_1,a_2=\frac{5\pm\sqrt5}2$$which are both irrational. Case 3: $n$ is composite Let $n=xy$ for positive integers $x,y\ge2$. Let $k=n+2-x-y$, $k$ is positive since: $$x+y\le x\cdot\frac y2+y\cdot\frac x2=n.$$Then, let $a_1=x$, $a_2=y$, and $a_i=1$ otherwise. Case 4: $n$ is prime and $n\ge11$ Let $k=\frac{n-1}2-1$ and $a_1=\frac n2$, $a_2=\frac12$, $a_3=4$, and $a_i=1$ otherwise. Case 5: $n=7$ Let $k=3$ and $a_1=\frac92$, $a_2=\frac43$, $a_3=\frac76$.
29.10.2022 01:08
Using $AM-GM$ gives that $\sum a_i \ge k \sqrt[k]{\prod a_i} \Rightarrow n^{k-1} \ge k^k \ge 4$, which gives that $n \neq 1,2,3,5$ Observe that we can use the number $1$ to full the difference between the sum and $n$ while not affecting $n$, Hence it motivates us to select some $a_1,a_2,..,a_i$ such that their sum and product is integer, hence it motivates us to use $n$'s factors Let $n=ab, a,b \in \mathbb{N}$, then let $a_1,a_2=a,b$, then take enough $1$'s so that $a+b+m=n$. But observe that $a+b>ab$ if $a=1$, hence it is only true for composite numbers. For prime numbers, select $a_1,a_2,a_3= \frac{n}{2},\frac{1}{2},4$ and fill the gaps with $1$s. (note that $2|n+1$). But the case $n=7$ is a exception since sum gives $8$. Hence it is enough to show a specific configuration for $7$. It is easy to prove $k=2$ is impossible. Hence assume that it has configuration for $k=3$. Then $a_1,a_2,a_3=\frac{7}{x} , \frac{xz}{y} ,\frac{y}{z}$ Now, it is matter of calculations ( starting from $\sum a_i =7$, to $2$). Starting from $x=2$ to $x=6$. Solving for $z$ for $x=2,3,4,5$ makes $z$ irrational, but if $x=6$, we have $z=\frac{3y}{4}, \frac{2y}{9}$ , since $y,z$ are integers, choose some $y$ that is divisible by $3$ or $2$, which gives $(y,z)=(4m,3m),(9m,2m)$, therefore we have $(a_1,a_2,a_3)=(\frac{7}{6},\frac{9}{2},\frac{4}{3})$ which clearly works, hence we are done . $\square$
12.11.2023 23:52
Solved with megarnie. Used the 30% hint on ARCH. The answer is $n=4$ or $n\ge 6$. If $n\le 3$, we have \[\sqrt[k]{n}=\sqrt[k]{a_1a_2\dots a_k}\le\frac{a_1+a_2+\dots+a_k}{k}=\frac{n}{k}.\]Thus if $k>n$, this is impossible. We can then manually check that this inequality is never satisfied when $2\le k\le n\le 3$. If $n=5$, with the inequality, we can check that only $k=2$ works out of $k\in\{2,3,4,5\}$. But solving for $a_1$ and $a_2$ result in irrational numbers, so this doesn't work either. For composite numbers $n$, let $p$ be its smallest prime factor and let $n=mp$. Then set $k=n-p-m+2$, $a_1=p$, $a_2=m$, $a_3=a_4=\dots=a_k=1$. Clearly this works(we only need to check that $n\ge p+m$ which is obvious). For prime $n\ge 11$, set $k=\frac{n-3}{2}$, $a_1=\frac n2$, $a_2=\frac12$, $a_3=4$, $a_4=a_5=\dots=a_k=1$. Clearly this works(we only need to check that $k\ge 3$ which is obvious). For $n=7$, use $a_1=\frac76$, $a_2=\frac43$, and $a_3=\frac92$. This completes our proof. $\blacksquare$
22.02.2024 02:42
All $n$ work except for $1$, $2$, $3$ and $5$. Clearly $1$ does not work. By AM-GM we have $\sqrt[k]{n} \geq \frac{n}{k}$. Let $p$ be some prime dividing $n$. Then if $n$ is composite then $a_1 = \frac{n}{p}$, $a_2 = p$, and then letting the rest of $a_i$ being $1$(until the sum of $a_i$ is $n$) works. If $n$ is prime then AM-GM gives $\sqrt[k]{n} \geq \frac{n}{k} \implies n \geq k^{k/(k-1)}$. From this we see that $n = 2, 3$ doesn't work. We also can find that $n = 5$ doesn't work by checking cases. If $n = 7$ then $a_1 = \frac{7}{6}$, $a_2 = \frac{3}{2}$, $a_3 = \frac{4}{3}$ and $a_4 = 3$ works. If $n$ is prime and is $\geq 11$, then $a_1 = \frac n2$, $a_2 = \frac 12$, $a_3 = 4$, and letting the rest of $a_i$ being $1$ works(until the total sum is $n$). Really boring problem
04.10.2024 21:01