OK, here is a fairly simple proof that for any positive integer $n$ and any positive real numbers $x_1,\ldots,x_n$,
$$ \sum_{i,j=1}^{n}\left\{\frac{x_i}{x_j}\right\}\leq \frac{9}{14}n^2\,.$$
That the constant $\frac{9}{14}$ cannot be improved has already been shown by the OP. I wonder if the Chinese student who invented the problem had the same one in mind.

Consider the function
$$
f(z)=\begin{cases}
1+z,&0\le z\le 1/2
\\
z+\frac 1z-1, &\frac 12\le z\le 2
\\
1+\frac 1z, &z\ge 2
\end{cases}
$$
Note that $f(z)=f(1/z)$ and $f(z)\ge\{z\}+\{1/z\}$ for all $z>0$. We shall show that
$$
\sum_{i,j}f(x_i/x_j)u_i u_j\le \frac 97\|u\|_{\ell^1}^2
$$
for all non-negative sequences $u$ with finite support and for all $x_j>0$.

Note that $f$ is a nice continuous function that is increasing near $0$, decreasing near $+\infty$ and *convex* except for two singular points $\frac 12$ and $2$. The last property allows one to choose any subset of $x_j$, replace them by $tx_j$ and move $t$ up or down to increase (or, at least, keep constant) the LHS until some ratio between the moving $x_j$ and the stationary ones becomes $2$ or $\frac 12$. Doing that a few times, we'll arrive to the situation when the graph in which $i$ is joined with $j$ if and only if $x_i/x_j\in\{\frac 12,2\}$ is connected (otherwise just move a connected component until acquiring a new edge). In normal English that means that all $x_j$ are just powers of $2$ (times some irrelevant positive common factor).

Thus, subtracting $1$ from each entry, we see that our matrix entries are just $2^{-|i-j|}$ for $i\ne j$ and $0$ for $i=j$. where $1\le i,j\le m$ (we unite the $u_j$ for colliding $x_j$, of course). Let's call that matrix $A(m)$. We want to show that
$$
\langle A(m)u,u\rangle=\sum_{i,j}A(m)_{ij}u_iu_j\le\frac 27\|u\|_{\ell^1}^2
$$
now.

It is time to move $u_i$. Notice first of all that we do not need zeroes in the middle: we can just move the support chunks together increasing the coefficient at each product $u_iu_j$ discarding the zero tail afterwards and reducing $m$. Next, assuming that we have full support, take some vector $v$ with sum $0$ and replace $u$ by $u+tv$. The RHS will not change until we kill one entry. The LHS will become
$$
\langle A(m)u,u\rangle+2t\langle A(m)u,v\rangle+t^2\langle A(m)v,v\rangle
$$
so, we cannot improve it and kill an entry only if $A(m)$ is negative definite on the zero sum subspace of $\mathbb R^m$. The last property fails for $m\ge 4$: just take $v=(2,1,-1,-2,0,0,\dots)$ to get $\langle A(m)v,v\rangle=0$. Thus we are interested in $m=2,3$ only. According to the last displayed formula, to find the optimal $u$, we need just to solve $A(m)u=e$ where $e$ is the vector of all $1$'s (the trivial instance of the Lagrange multiplier idea). For $m=2$, we get $u=(2,2)$ with the constant $\frac 14$ (Alexei's example). For $m=3$, we get $u=(1,\frac 32,1)$ and the ratio $\frac 27$ (the Chinese student example).

That's it.

13more comments