Prove that $\sum_{1\le iLet $n \ge 2$ be a an integer and $x_1,...,x_n$ are positive reals such that $$\sum_{i=1}^nx_i=\frac{1}{2}$$
Prove that
$$\sum_{1\le i<j\le n}\frac{x_ix_j}{(1-x_i)(1-x_j)}\le \frac{n(n-1)}{2(2n-1)^2}$$
Here is the source of the problem (in french) here
Edit:
I'll present my best bound yet on $$\sum_{1\le i<j\le 1}\frac{x_ix_j}{(1-x_i)(1-x_j)}=\frac{1}{2}\left(\sum_{k=1}^n\frac{x_k}{1-x_k}\right)^2-\frac{1}{2}\sum_{k=1}^n\frac{x_k^2}{(1-x_k)^2}$$
This formula was derived in @GCab's Answer.
First let $a_k=x_k/(1-x_k)$
so we want to prove
$$\left(\sum_{k=1}^na_k\right)^2-\sum_{k=1}^na_k^2\le \frac{n(n-1)}{(2n-1)^2}$$
But since $$\frac{x_k}{1-x_k}<2x_k\implies \sum_{k=1}^na_k<1 \quad (1)$$
Hence $$\left(\sum_{k=1}^na_k\right)^2\le \sum_{k=1}^na_k$$
Meaning $$\left(\sum_{k=1}^na_k\right)^2-\sum_{k=1}^na_k^2\le\sum_{k=1}^na_k(1-a_k)$$
Now consider the following function $$f(x)=\frac{x}{1-x}\left(1-\frac{x}{1-x}\right)$$
$f$ is concave on $(0,1)$ and by the tangent line trick we have $$f(x)\le f'(a)(x-a)+f(a)$$
set $a=1/2n$ to get $$a_k(1-a_k)\le\frac{4n^2\left(2n-3\right)}{\left(2n-1\right)^3}\left(x_k-\frac{1}{2n}\right)+ \frac{2(n-1)}{(2n-1)^2}$$
Now we sum to finish $$\sum_{k=1}^na_k(1-a_k)\le \frac{2n(n-1)}{(2n-1)^2}$$
Maybe by tweaking $(1)$ a little bit we can get rid of this factor of $2$
 A: Edit. Eventhough I had in mind the version of the ACM I needed, it all messed up when I tried to find a reference. As for the valid version, I will refer to Vasile Cirtoaje's Algebraic Inequalities. Old and new Methods, p. $267$.

We will employ a powerful technique developed by Vasile Cirtoaje back in $2006$ called the Arithmetic Compensation Method (see, for instance, this document).
Let to this end $$F(x_1, \ldots, x_n):=\sum_{1\leqslant i<j\leqslant n}\frac{x_ix_j}{(1-x_i)(1-x_j)}$$ which is clearly symmetric and continuous on $S:=\left\{(x_1, \ldots,x_n)\mid \sum_{i=1}^n x_i=\frac12, \forall i: x_i\geqslant 0\right\}$. We will now refer to the Remark 1.1 from the document linked above, which basically states that

If $$F(x_1,x_2,x_3,\ldots,x_n)>F\left(\frac{x_1+x_2}2, \frac{x_1+x_2}{2}, x_3,\ldots,x_n\right)\label{(i)}\tag{i}$$
implies $F(x_1,x_2,x_3,\ldots,x_n)\leqslant F(0, x_1+x_2, x_3, \ldots, x_n)$, then $$F(x_1,x_2,x_3,\ldots,x_n)\leqslant \underset{1\leqslant k\leqslant n}\max F\left(\frac1{2k}, \ldots, \frac1{2k},0,\ldots ,0\right)$$

Notice that (\ref{(i)}) is equivalent to (where we will denote, for brevity, $y:=\frac{1}2(x_1+x_2)$)
\begin{align*}
\frac{x_1x_2}{(1-x_1)(1-x_2)}-\frac{y^2}{(1-y)^2}+\left(\frac{x_1}{1-x_1}+\frac{x_2}{1-x_2}-\frac{2y}{1-y}\right)\sum_{i=3}^n \frac{x_i}{1-x_i}>0\\
\iff \frac{y^2-x_1x_2}{(1-x_1)(1-x_2)(1-y)^2}\left[2y-1+2(1-y)\sum_{i=3}^n \frac{x_i}{1-x_i}\right]>0\\
\iff 2y-1+2(1-y)\sum_{i=3}^n \frac{x_i}{1-x_i}>0
\end{align*}
Where the last equivalence follows from $y^2-x_1x_2\geqslant 0$. We will now turn to the second inequality:
\begin{align*}
F(x_1,x_2,x_3,\ldots,x_n)- F(0, x_1+x_2, x_3, \ldots, x_n)\leqslant0\\
\iff \frac{x_1x_2}{(1-x_1)(1-x_2)}+\left(\frac{x_1}{1-x_1}+\frac{x_2}{1-x_2}-\frac{2y}{1-y}\right)\sum_{i=3}^n \frac{x_i}{1-x_i}\leqslant0\\
\iff \frac{x_1x_2}{(1-x_1)(1-x_2)(1-2y)}\left[1-2y+2(y-1)\sum_{i=3}^n \frac{x_i}{1-x_i}\right]\leqslant 0\\
\end{align*}
Which is easily seen to follow from (\ref{(i)}). Thus, we conclude that \begin{align*}
F(x_1,x_2,x_3,\ldots,x_n)&\leqslant \underset{1\leqslant k\leqslant n}\max F\left(\frac1{2k}, \ldots, \frac1{2k},0,\ldots ,0\right)\\
&= \underset{1\leqslant k\leqslant n}\max  \binom{k}{2}\frac{1}{(2k-1)^2}\\
&= \underset{1\leqslant k\leqslant n}\max  \frac{k(k-1)}{2(2k-1)^2}
\end{align*}
But $f: x\mapsto \frac{x(x-1)}{2(2x-1)^2}$ is increasing on $[1,\infty)$, and, hence, the result follows.
Remark. Based on the difficulty of the other contest problems, this solution seems a bit overkill to me, but I have failed in the attempt to find a simpler method, since most well-known inequalities work in the other direction...
A: You should be able to look for the maximum, by the method of Lagrange. We set
$$F(x_1,...,x_n) \equiv \sum_{i\neq j} \frac{x_i x_j}{(1-x_i)(1-x_j)} \stackrel{\text{wts.}}{\leq} \frac{n(n-1)}{(2n-1)^2} \, ,$$
and define the Lagrange-function as $$L(x_1,...,x_n) = F(x_1,...,x_n) - \lambda \left(x_1+...+x_n-1/2\right) \,.$$
At an extremum we have $$\nabla L = 0 \qquad , \qquad \nabla=\begin{pmatrix} \partial_{x_1} \\ \vdots \\ \partial_{x_n} \\ \partial_\lambda\end{pmatrix} \, ,$$
in coordinates
\begin{align}\frac{2}{(1-x_k)^2} \sum_{\substack{i=1 \\ i\neq k}}^n \frac{x_i}{1-x_i} &= \lambda \quad\text{for}\quad k=1,...,n  \tag{1} \\ 
\sum_{i=1}^n x_i &= 1/2 \tag{2} \, .\end{align}
Multiplying Equation (1) by $\frac{(1-x_k)^2}{2}$ and adding $\frac{x_k}{1-x_k}$ to both sides gives
$$c=\sum_{i=1}^n \frac{x_i}{1-x_i} = \frac{\lambda}{2} (1-x_k)^2 + \frac{x_k}{1-x_k} \tag{3}$$
where the sum on the LHS is now independent on $k$ and we can consider it as a constant $c$. We now sum (3) from $k=1$ to $n$
\begin{align}
nc&=\frac{\lambda}{2} \left( n - 1 + \sum_{k=1}^n x_k^2\right) + c \\
\Rightarrow \quad c&= \frac{\lambda}{2} + \frac{\lambda}{2(n-1)} \sum_{k=1}^n x_k^2 > \frac{\lambda}{2} \tag{4}
\end{align}
which we will need to use in a second. Rearranging Equation (3) gives a monic polynomial in $x_k$
$$x_k^3 - 3x_k^2 + \left( 3 - \frac{2+2c}{\lambda} \right)x_k + \frac{2c}{\lambda} - 1 = 0 \, . \tag{5}$$
A cubic can have either only 1 real solution, in which case there is nothing to show, since then $x_1=...=x_n$ follows, or it can have 3 real solutions. In this case there appears to be a great variety of combinations of the three roots for the various $x_k$. However, since the product of the three roots is equal to $1-\frac{2c}{\lambda}<0$ by Equation (4) and (5), either all three roots are negative (discard), or only one root is negative and we are left with two choices for the various $x_k$. But then, since the sum of all three roots is equal to $3$ by Equation (5) and one root is negative, the sum of the two positive roots must be strictly greater than $3$. This implies, that at least one of them is strictly greater than $1/2$, which stands in contradiction to Equation (2). Thus, we are left with only one valid real solution satisfying Equation (2) and $$x_1=...=x_n=x$$
follows. It is then easy to see that $x=1/2n$.
It remains to show, that this extremal point is actually a maximum. The hessian of $L$ is given in coordinates by
$$\frac{1}{2} \, {\rm Hess}_{k,l} (L) = \frac{2\delta_{k,l}}{(1-x_k)^3} \sum_{i\neq k} \frac{x_i}{1-x_i} + \frac{1-\delta_{k,l}}{(1-x_k)^2(1-x_l)^2} \qquad \text{for} \qquad k,l=1,...,n \\
\frac{1}{2} \, {\rm Hess}_{n+1,k} (L) = \frac{1}{2} \, {\rm Hess}_{k,n+1} (L) = -1 \qquad \text{for} \qquad k=1,...,n \\
\frac{1}{2} \, {\rm Hess}_{n+1,n+1} (L) = 0 \, .$$
With $x_k=x=1/2n$ the first line becomes
$$\frac{1}{2} \, {\rm Hess}_{k,l} (L) = \frac{1-\frac{\delta_{k,l}}{n}}{\left(1-\frac{1}{2n}\right)^4} \qquad \text{for} \qquad k,l=1,...,n$$
and in matrix-form this looks like
$$\frac{1}{2} \, {\rm Hess} (L) = \frac{1}{\left(1-\frac{1}{2n}\right)^4} \begin{pmatrix} 
1-1/n & 1 & \dots & 1 & -1 \\
1 & 1-1/n & \dots & 1 & -1 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
1 & 1 & \dots & 1-1/n & -1 \\
-1 & -1 & \dots & -1 & 0  \end{pmatrix} \, .$$
Then, defining the variational vector $\epsilon=(\epsilon_1,...,\epsilon_n,\epsilon_\lambda)^t$, we find for the second variation
$$\frac{1}{2} \sum_{k,l=1}^{n+1} \epsilon_k \, {\rm Hess}_{k,l} (L) \, \epsilon_l = - \frac{\sum_{k=1}^n \epsilon_k^2/n}{\left(1-\frac{1}{2n}\right)^4}<0$$ $\forall \epsilon \in {\mathbb R}^{n+1}$ satisfying
$$\sum_{k=1}^n \epsilon_k = 0 \, ,$$
which is a consequence of Equation (2).
A: I found the AoPS link https://artofproblemsolving.com/community/c6h2503722p21150538.
It is a problem from "Problems From the Book", 2008, Ch. 2, which was proposed by Vasile Cartoaje. The proof there is very nice. I put the proof here.
Let us write the inequality as
$$\left(\sum_{i=1}^n \frac{x_i}{1 - x_i}\right)^2 \le \sum_{i=1}^n \frac{x_i^2}{(1 - x_i)^2} + \frac{n(n-1)}{(2n-1)^2}.$$
Using Cauchy-Bunyakovsky-Schwarz inequality, we have
$$\left(\sum_{i=1}^n \frac{x_i}{1 - x_i}\right)^2
\le \left(\sum_{i=1}^n x_i\right)
\left(\sum_{i=1}^n \frac{x_i}{(1-x_i)^2}\right)
= \sum_{i=1}^n \frac{x_i/2}{(1-x_i)^2}.$$
Thus, it suffices to prove that
$$\sum_{i=1}^n \frac{x_i/2}{(1-x_i)^2} \le \sum_{i=1}^n \frac{x_i^2}{(1 - x_i)^2} + \frac{n(n-1)}{(2n-1)^2}$$
or
$$\sum_{i=1}^n \frac{x_i(1 - 2x_i)}{(1-x_i)^2} \le \frac{2n(n-1)}{(2n-1)^2}.$$
Note that $x \mapsto \frac{x(1-2x)}{(1-x)^2}$ is concave on $[0, 1/2]$.
Using Jensen's inequality, the desired result follows.
A: Hint:
Indicating as $S_n , \, T_n$
$$
\begin{array}{l}
 T_n  = \sum\limits_{1 \le i < j \le n} {a_i a_j }  \\ 
 S_n  = \sum\limits_{1 \le i,j \le n} {a_i a_j }
  = \sum\limits_{1 \le i \le n} {\sum\limits_{1 \le j \le n} {a_i a_j } }
  = \sum\limits_{1 \le i \le n} {a_i } \sum\limits_{1 \le j \le n} {a_j }
  = \left( {\sum\limits_{1 \le i \le n} {a_i } } \right)^2  \\ 
 \end{array}
$$
then you also have that
$$
\begin{array}{l}
 S_n  = \sum\limits_{1 \le i,j \le n} {a_i a_j }
  = \sum\limits_{1 \le i < j \le n} {a_i a_j }  + \sum\limits_{1 \le i = j \le n} {a_i a_j }
  + \sum\limits_{1 \le j < i \le n} {a_i a_j }  =  \\ 
  = 2T_n  + \sum\limits_{1 \le i \le n} {a_i ^2 }  \\ 
 \end{array}
$$
