Find the tight upper bound of $\sum_{i=1}^n \frac{i}{i+x_i}$, where the $x_i$'s are distinct in $\{1,2,...,n\}$

Question

What is the tight upper bound of $\sum_{i=1}^n \frac{i}{i+x_i}$, where the $x_i$'s are distinct integers in $\{1,2,...,n\}$?

Answer 1

I doubt that there is an exact formula for this maximum, and unfortunately Wolfgang's guess is incorrect. Indeed, let $$ a_n = \mathrm{max}_{\sigma \in \mathfrak{S}_n} \sum_{i=1}^n \frac{i}{i + \sigma(i)}. $$ Then by considering the standard embedding $\mathfrak{S}_n \times \mathfrak{S}_m \hookrightarrow \mathfrak{S}_{n+m}$, one checks that $$ a_{n+m} \geq a_n + a_m, $$ so that the sequence $\frac{a_n}{n}$ converges to the number $c = \mathrm{sup}_n \frac{a_n}{n} \in [\frac{1}{2},1]$. Now, I claim that $c > \frac{1}{2}$, so that neither $\mathrm{id}$ nor $(n, 1, 2,...,n-1)$ grant the maximum when $n$ is large.

For $r = r_n = \lfloor \alpha n \rfloor$ with $\alpha \in ]0,1[$, let us consider the cycle $(n-r+1,n-r+2,...,n-1,n,1,2,...,n-r)$. Then we get \begin{align*} c &\geq \lim_n \frac{1}{n} \left( \sum_{j=1}^r \frac{j}{n-r+2j} + \sum_{j=r+1}^n \frac{j}{2j-r} \right) \\ &= \frac{1}{2} + \frac{\alpha}{4} \log \left( \frac{2-\alpha}{\alpha} \right) - \frac{1-\alpha}{4} \log \left( \frac{1+\alpha}{1-\alpha} \right) . \end{align*} This is $> \frac{1}{2}$ for $\alpha \in ]0, \frac{1}{2}[$. The maximum is around $\alpha = 0.14868$, where the bound is $c >0.529$.

Answer 2

Most surely, (see bottom) Initially I had thought $$max=\frac1{1+n}+\sum_{i=2}^n \frac i{i+(i-1)},$$ but my proof below is still somewhat incomplete...

If the $x_i$ are a permutation $\pi$ of $\{1,2,...,n\}$, let $y_i:=\pi^{-1}(i)$ Then we have $$\sum_{i=1}^n \frac{i}{i+x_i}=n-\sum_{i=1}^n \frac{x_i}{i+x_i}=n-\sum_{j=1}^n \frac{j}{y_j+j},$$ so the sums come in pairs, and if $\pi$ yields a maximum, then $\pi^{-1}$ will yield a minimum.

I'd like to show that the maximum is attained for the permutation ${\pi:=(n,1,2,...,n-1)}$.

Now, for $i>1$ and $k<n$, $$\frac1{1+n}+\frac i{i+k}>\frac 1{1+k}+\frac i{i+n}$$because $$LHS-RHS=\frac{(i - 1) (n-k) (k n - i)}{(1+n) (i + k)(1+k) (i + n)}>0.$$ So we must have $x_1=n$ for a maximal permutation.

Generally, $$\frac j{j+a}+\frac k{k+b}-\left(\frac j{j+b}+\frac k{k+a}\right) =\frac{(b-a)(k-j)(jk-ab)}{(j+a) (k+b) (j+b)(k+a)}.$$ Thus if for $j\ge2$ we put $x_j=j-1$, the above difference (with putting $a=x_j, b=x_k$) is always positive. This proves that $\pi$ does strictly better than with any involution applied to it, which gives a strong evidence in favor of $\pi$.
But the problem remains that we cannot conclude from there for any combination of involutions because of the factor $(jk-ab)$ which might become negative at some point.

EDIT after js21's answer: That shot was too quick. It looks in fact like the maximum is attained for the permutation $$\color{red}{\pi_k=[n,n-1,...,n-k+1,1,2,...,n-k]}$$ with $k\approx \dfrac n{6.3032}$, thus linear in $n$. This is very precise: for $n<1,000,000$, the optimal $k$ always seems to be within a range $\pm1$ of this fraction, even for small $n$.