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\}$?

4$\begingroup$ Are you asking for the maximum of $f:S_{n}\rightarrow\mathbb{R}:\sigma\mapsto\sum_{i=1}^{n}\frac{i}{i+\sigma(i)}$? $\endgroup$ – Nicéphore Bayekula Nov 1 '18 at 9:08
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,...,n1)$ 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 $(nr+1,nr+2,...,n1,n,1,2,...,nr)$. Then we get \begin{align*} c &\geq \lim_n \frac{1}{n} \left( \sum_{j=1}^r \frac{j}{nr+2j} + \sum_{j=r+1}^n \frac{j}{2jr} \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$.

$\begingroup$ Here are the first few maxima: $([1], 1/2)$, $([1, 2], 1), ([2, 1], 1)$, $([3, 1, 2], 91/60)$, $([4, 1, 2, 3], 214/105)$, $([5, 1, 2, 3, 4], 1613/630)$, $([6, 1, 2, 3, 4, 5], 10679/3465)$, $([7, 1, 2, 3, 4, 5, 6], 1298221/360360)$, $([8, 7, 1, 2, 3, 4, 5, 6], 3469/840)$, $([9, 8, 1, 2, 3, 4, 5, 6, 7], 2609/560)$, $([10, 9, 1, 2, 3, 4, 5, 6, 7, 8], 287579/55440)$ $\endgroup$ – Martin Rubey Nov 2 '18 at 16:17

$\begingroup$ In fact, if this pattern persists, then the maximum would be $\frac{1}{4} \, r {\left(H_{n  r/2}  H_{r/2}  2\right)} + \frac{1}{2} \, n + \frac{r(r+1)}{2 \, {\left(n + 1\right)}}$ for some $r$, where $H_k$ is the harmonic number. $\endgroup$ – Martin Rubey Nov 2 '18 at 16:39
Most surely, (see bottom) Initially I had thought $$max=\frac1{1+n}+\sum_{i=2}^n \frac i{i+(i1)},$$ 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,...,n1)}$.
Now, for $i>1$ and $k<n$, $$\frac1{1+n}+\frac i{i+k}>\frac 1{1+k}+\frac i{i+n}$$because $$LHSRHS=\frac{(i  1) (nk) (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{(ba)(kj)(jkab)}{(j+a) (k+b) (j+b)(k+a)}.$$ Thus if for $j\ge2$ we put $x_j=j1$, 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 $(jkab)$ 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,n1,...,nk+1,1,2,...,nk]}$$ 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$.

$\begingroup$ How can you check that the maximum for such a large $n$ is of the given form? Besides, I think that @js21 considered a different permutation (which yields a large value, but not the maximum)... $\endgroup$ – Martin Rubey Nov 2 '18 at 22:08

$\begingroup$ @MartinRubey Of course, like for most conjectures, there is a certain amount of educated guess involved. I have not checked millions of sums, I just say "it looks like", but I don't claim... One of my assumptions is a kind of monotonicity, which seems highly plausible: if for a fixed $n$, we take $\pi_k:=[n,n1,...,nk+1,1,2,...,nk]$, then there is a $k$ such that $f(\pi_1)<\cdots<f(\pi_k)>f(\pi_{k+1}>\cdots$. And the first $\pi_k$ seem to be the best candidates, so... My "indeed" referred rather to your first comment there than to js21's permutations. :) In any case, we must have $x_1=n$. $\endgroup$ – Wolfgang Nov 3 '18 at 13:10

$\begingroup$ OK, I just thought you had some way to check that the general form I mentioned in the comment was correct. By the way, the poset of permutations ordered by $f$ is quite interesting! $\endgroup$ – Martin Rubey Nov 3 '18 at 13:25

$\begingroup$ Another comment: if I made no mistake, given the conjectural form, I think that $k\simeq c\cdot n$ should be such that $c$ is the zero of $(c2)\ln(\frac{c}{2}1) + 2(2c3)(c1)$. So, $1/c=6.303250770424045$ as you write. $\endgroup$ – Martin Rubey Nov 3 '18 at 13:31

$\begingroup$ @MartinRubey That sounds good. How did you come up with that? I suppose by solving $f(\pi_k)=f(\pi_{k+1})$ for big n, using asymptotics of the harmonic series? $\endgroup$ – Wolfgang Nov 3 '18 at 16:46