62nd Ukrainian National Mathematical Olympiad

We will show that the desired $C$ is the positive root of the equation $x^2+x=1$, $C=\frac{\sqrt{5}-1}{2}$.

First, suppose that for some positive integers $x<y$ the inequalities $\sqrt{x^2+2y}>C$, $\{\sqrt{y^2+2x}\}>C$ hold. Note that $y^2<y^2+2x<(y+1{)}^2$, so we have $y^2+2x>(y+C{)}^2\iff 2x>2Cy+C^2\Rightarrow x>Cy$. Then $(x+1{)}^2<x^2+2y<x^2+\frac{2}{C}x<x^2+4x<(x+2{)}^2$.

So $x^2+2y>(x+1+C{)}^2\iff 2y>2(C+1)x+(C+1{)}^2\Rightarrow y>(C+1)x$. But then $xy>xy\cdot C(C+1)=xy$: a contradiction.

Now let's show that any $C_1<C$ does not satisfy the condition. Consider $y=[(C+1)x]$ for some sufficiently large $x$. We show that starting from some $x$ we have $\sqrt{x^2+2y}>C_1$, $\sqrt{y^2+2x}>C_1$. It is easy to see that $y^2<y^2+2x<(y+1{)}^2$ and also $(x+1{)}^2<x^2+2y<(x+2{)}^2$ so it suffices to show that for sufficiently large $x$ it holds that $x^2+2y>(x+1+C_1{)}^2$, $y^2+2x>(y+C_1{)}^2$. These inequalities are equivalent to the following: $2y>2x(C_1+1)+(C_1+1{)}^2$, $2x>2y{C}_1+C_1^2$. Note that $2y-2x(C_1+1)\ge 2x(C+1)-2-2x(C_1+1)=2x(C-C_1)-2$ which is greater than $(C_1+1{)}^2$ for a sufficiently large $x$. Also note that $2x-2y{C}_1<2x-2x(C+1)C_1=x(2-(C+1)C_1)$. Since $(C+1)C_1<(C+1)C=1$, this value is greater than $C_1^2$ for a sufficiently large $x$.