Numbers $1$ through $2014$ are written on a board. A valid operation is to erase two numbers $a$ and $b$ on the board and replace them with the greatest common divisor and the least common multiple of $a$ and $b$. Prove that, no matter how many operations are made, the sum of all the numbers that remain on the board is always larger than $2014$ $\times$ $\sqrt[2014]{2014!}$
Problem
Source:
Tags: inequalities, number theory, least common multiple, invariant, greatest common divisor, combinatorics unsolved, combinatorics
23.08.2014 05:24
Claim: $\left( \dfrac{2015}{2} \right)^{2014} > 2014!$ By AM-GM, we know that $\dfrac{a + (2015-a)}{2} > \sqrt{a(2015-a)}$ for all positive $a \neq \dfrac{2015}{2}$, which includes all integers $1,2,\ldots,1007$. Thus we obtain $\left( \dfrac{2015}{2} \right)^2 > a(2015-a)$ for all $a = 1,2,\ldots,1007$. Multiplying all these inequalities gives us the desired claim. Claim: $\gcd(a,b) + \text{lcm}(a,b) \ge a+b$ WLOG $a \le b$. Observe that $\gcd(a,b) \le \min(a,b) = a$, and $\text{lcm}(a,b) = \dfrac{ab}{\gcd(a,b)}$, and $b = \dfrac{ab}{a}$. Thus, define $f(x) = x + \dfrac{ab}{x}$, then LHS is $f(\gcd(a,b))$ and RHS is $f(a)$. But $f$ is decreasing for $x \in (0, \sqrt{ab}]$, and since $\gcd(a,b), a \in (0, \sqrt{ab}]$ and $\gcd(a,b) \le a$, we have $f(\gcd(a,b)) \ge f(a)$, thus the claim. For the proof: Observe that the sum of numbers don't decrease by our second claim, so the sum of numbers is at least $\dfrac{2014 \cdot 2015}{2}$. Now, by the first claim, $\left( \dfrac{2015}{2} \right)^{2014} > 2014!$, so $\dfrac{2015}{2} > \sqrt[2014]{2014!}$ and so $\dfrac{2014 \cdot 2015}{2} > 2014 \cdot \sqrt[2014]{2014!}$, proving the statement.
23.08.2014 07:27
Observe that product of the numbers is invariant since $ab=\text{lcm}(a,b)\cdot\gcd(a,b)$. Let the sequence of numbers after a sequence of moves be $a_1,\cdots,a_{2014}$. Then by AM-GM, we have \[a_1+\cdots+a_{2014}\ge 2014\cdot \sqrt[2014]{a_1\cdot\cdots\cdot a_{2014}}=2014\cdot\sqrt[2014]{2014!}.\]
23.08.2014 20:34
Let be a and b, positives integers a=a'k and b=b'k where mcd(a',b')=1 so mcd(a,b)=k and mcm(a,b)=a'b'k so it's easy to show that mcd(a,b)+mcm(a,b) = k(1+a'b')>= k(a'+b') so when we change the numbers the sum grows so it's enough to show that 1+...+2014> $ \sqrt[2014]{2014!} $ but it's obvius by AM-GM, the equality can't held because of all the terms can't be equal, so we're done.
07.10.2019 13:55
Draco wrote: Observe that product of the numbers is invariant since $ab=\text{lcm}(a,b)\cdot\gcd(a,b)$. Let the sequence of numbers after a sequence of moves be $a_1,\cdots,a_{2014}$. Then by AM-GM, we have \[a_1+\cdots+a_{2014}\ge 2014\cdot \sqrt[2014]{a_1\cdot\cdots\cdot a_{2014}}=2014\cdot\sqrt[2014]{2014!}.\] Once we have this, we need to show equality can't be attained. To show this, note that the number $1$ will always remain on the board (since $\gcd(1,n)=1$. Hence equality is attained only when all the numbers are equal, namely to 1, which is clearly absurd.