Let $a_1, a_2, \ldots, a_n$ be $n$ positive integers that are not divisible by each other, i.e. for any $i \neq j$, $a_i$ is not divisible by $a_j$. Show that \[ a_1+a_2+\cdots+a_n \ge 1.1n^2-2n. \] Note: A proof of the inequality when $n$ is sufficient large will be awarded points depending on your results.
Problem
Source: 2022 China TST, Test 2, P3
Tags: inequalities, number theory, Divisibility
28.03.2022 12:50
This isn't a complete solution. Its a very stupid bounding idea. It proves the bound $n^2-2n$. Idk if you can optimise it in the current form. Order the numbers in increasing order. Fix $k \geqslant 2$. If $a_k \leqslant 2(k-2)$ then by the Piegon-Hole Principle some two among $a_1, a_2, \cdots, a_{k-1}$ violate the given constraints. Thus each $a_k \geqslant 2k-3$ for $k \geqslant 2$. Summing this we get a bound of $n^2-2n$, which fails. (how nice)
28.03.2022 13:50
Well, an even simpler argument gives the bound $n^2$ already: Just note that all the odd parts of the $a_i$ have to be distinct and so their sum is at least $1+3+5+7+\dots+(2n-1)=n^2$.
28.03.2022 20:00
Wow this is very hard, the best constant I could bound right now is 29/27.
29.03.2022 10:55
In fact it is impossible to replace 1.1 by a constant greater than 8/7
01.04.2022 10:32
With Justanaccount's help, I think? I have an approach that proves if the problem is true for all $n\le C$ then we can apply induction. My current constant for $n^2$ is approximately $1.1+2*10^{-5}$ (with around $10^{-5}$) error) This method only considers $\nu_3$ and odd parts, so it can be improved in many ways. bruh
01.04.2022 11:43
Would you like to pose your solution, or at least a sketch?
02.04.2022 12:29
A high class problem
03.04.2022 07:55
Partial solution with Desmos and Justanaccount that proves if the statement is true for all $n<C$ then it must be true for all $n$ by strong induction on $n$. Because my solution seems a bit sketchy, if there are any mistakes in my solution, please point it out. Thank you!
I may have typoed on desmos... I'll check again tomorrow.
04.04.2022 10:43
I've worked out the best constant for $n^2$ is $\frac{3}{2 \sum_{i=1}^{+\infty} \frac{1}{3^i-2^i-3^{i-1}+2^{i-1}}}$, which is approximately 1.10841.
04.04.2022 12:37
@above, did you mean that it was the best constant one could prove or you managed to prove that the sum is greater than 1.10841n^2? If it is the second case would you mind posting the solution please? I'm interested in a complete solution.
04.04.2022 14:38
@above Well, I almost proved it but still have some little problems.
04.04.2022 19:30
Andyqian7 wrote: I've worked out the best constant for $n^2$ is $\frac{3}{2 \sum_{i=1}^{+\infty} \frac{1}{3^i-2^i-3^{i-1}+2^{i-1}}}$, which is approximately 1.10841. Extraordinary...
05.04.2022 10:02
15.04.2022 22:55
For proving bound for sufficiently large $n$, it's enough to show that: $\sum_{i=1}^{\infty} 3k (3^{x_k}-2^{x_k}) \geq 1.1n^2 - 2n$ for any sequence of non-negative integers $x_k$ satisfying $\sum_{i=1}^{\infty}x_i=n$
03.07.2022 02:48
As noted above it suffices to prove that $\sum_{k=1}^{\infty} 3k (3^{x_k}-2^{x_k}) \geq 1.1n^2 - 2n$ for non-negative integers satisfying $\sum_{i=1}^{\infty}x_i=n$. To this end the following works surprisingly well. Write ($a$ is to be chosen later) $$\sum_{k=1}^{\infty} 3k (3^{x_k}-2^{x_k})=\sum_{k=1}^{\infty} (3k (3^{x_k}-2^{x_k})-anx_k) +an^2\ge \sum_{k=1}^{\infty} \min(3k (3^{s}-2^{s})-ans)+an^2 $$Because $3k(3^x-2^x)-anx$ is a convex function of $x$ and $3k(3^s-2^s)-ans$ is a convex sequence for $s=0,1,2,...$ we have the following $ \min(3k (3^{s}-2^{s})-ans)=\sum_{s=1}^{\infty}((3k(3^s-2^s)-ans)-(3k(3^{s-1}-2^{s-1}-an(s-1)))^{-}=\sum_{s=1}^{\infty}(3k(2\cdot 3^{s-1}-2^{s-1})-an)^{-}$ where $(x)^{-}=x$ if $x<0$ and $0$ otherwise. So continuing the above $$\sum_{k=1}^{\infty} \min(3k (3^{s}-2^{s})-ans)+an^2=\sum_{k=1}^{\infty} \sum_{s=1}^{\infty}(3k(2\cdot 3^{s-1}-2^{s-1})-an)^{-}+an^2=$$$$\sum_{s=1}^{\infty}\sum_{k<\frac{an}{3(2\cdot 3^{s-1}-2^{s-1})}}(3k(2\cdot 3^{s-1}-2^{s-1})-an)+an^2=\sum_{s=1}^{\infty}-\frac{1}{6} \frac{a^2n^2}{(2\cdot 3^{s-1}-2^{s-1})}+an^2+o(n^2)=(a-\frac{c}{6}a^2)n^2+o(n^2)$$for $c=\sum_{i=0}^{\infty}\frac{1}{2\cdot 3^i-2^i}$ of course then we choose $a=\frac{3}{c}$ and we get a bound of the form $(\frac{3}{2c}+o(1))n^2$ By looking at first few terms you can get that $c<4/3+1/50$ and then $\frac{3}{2c}>1.1$ approximately $9/8$