IMO 2019 Shortlisted Problems

Solution 1 (Lagrange interpolation). Since both sides of the identity are rational functions, it suffices to prove it when all $x_i\notin \{\pm 1\}$. Define $$f(t)=\prod _{i=1}^n\left(1-x_{i}t\right)$$ and note that $$f\left(x_i\right)=\left(1-x_i^2\right)\prod _{j\ne i}1-x_i{x}_j$$ Using the nodes $+1,-1,x_1,\dots ,x_n$, the Lagrange interpolation formula gives us the following expression for $f$ : $$\sum _{i=1}^{n}f\left(x_i\right)\frac{(x-1)(x+1)}{\left(x_i-1\right)\left(x_i+1\right)}\prod _{j\ne i}\frac{x-x_j}{x_i-x_j}+f(1)\frac{x+1}{1+1}\prod _{1⩽i⩽n}\frac{x-x_i}{1-x_i}+f(-1)\frac{x-1}{-1-1}\prod _{1⩽i⩽n}\frac{x-x_i}{1-x_i}.$$ The coefficient of $t^{n+1}$ in $f(t)$ is 0 , since $f$ has degree $n$. The coefficient of $t^{n+1}$ in the above expression of $f$ is $$\begin{array}{rl}0& =\sum _{1⩽i⩽n}\frac{f\left(x_i\right)}{{\prod }_{j\ne i}\left(x_i-x_j\right)\cdot \left(x_i-1\right)\left(x_i+1\right)}+\frac{f(1)}{{\prod }_{1⩽j⩽n}\left(1-x_j\right)\cdot (1+1)}+\frac{f(-1)}{{\prod }_{1⩽j⩽n}\left(-1-x_j\right)\cdot (-1-1)}\\ & =-G\left(x_1,\dots ,x_n\right)+\frac{1}{2}+\frac{(-1{)}^{n+1}}{2}\end{array}$$

Solution 2 (using symmetries). Observe that $G$ is symmetric in the variables $x_1,\dots ,x_n$. Define $V={\prod }_{i<j}\left(x_j-x_i\right)$ and let $F=G\cdot V$, which is a polynomial in $x_1,\dots ,x_n$. Since $V$ is alternating, $F$ is also alternating (meaning that, if we exchange any two variables, then $F$ changes sign). Every alternating polynomial in $n$ variables $x_1,\dots ,x_n$ vanishes when any two variables $x_i,x_j(i\ne j)$ are equal, and is therefore divisible by $x_i-x_j$ for each pair $i\ne j$. Since these linear factors are pairwise coprime, $V$ divides $F$ exactly as a polynomial. Thus $G$ is in fact a symmetric polynomial in $x_1,\dots ,x_n$. Now observe that if all $x_i$ are nonzero and we set $y_i=1/x_i$ for $i=1,\dots ,n$, then we have $$\frac{1-y_i{y}_j}{y_i-y_j}=\frac{1-x_i{x}_j}{x_i-x_j}$$ so that $$G\left(\frac{1}{x_1},\dots ,\frac{1}{x_n}\right)=G\left(x_1,\dots ,x_n\right)$$ By continuity this is an identity of rational functions. Since $G$ is a polynomial, it implies that $G$ is constant. (If $G$ were not constant, we could choose a point $\left(c_1,\dots ,c_n\right)$ with all $c_i\ne 0$, such that $G\left(c_1,\dots ,c_n\right)\ne G(0,\dots ,0)$; then $g(x):=G\left(c_{1}x,\dots ,c_{n}x\right)$ would be a nonconstant polynomial in the variable $x$, so $|g(x)|\to \infty$ as $x\to \infty$, hence $\left|G\left(\frac{y}{c_1},\dots ,\frac{y}{c_n}\right)\right|\to \infty$ as $y\to 0$, which is impossible since $G$ is a polynomial.) We may identify the constant by substituting $x_i={\zeta }^i$, where $\zeta$ is a primitive $n^{\text{th}}$ root of unity in $\mathbb{C}$. In the $i^{\text{th}}$ term in the sum in the original expression we have a factor $1-{\zeta }^i{\zeta }^{n-i}=0$, unless $i=n$ or $2i=n$. In the case where $n$ is odd, the only exceptional term is $i=n$, which gives the value ${\prod }_{j\ne n}\frac{1-{\zeta }^j}{1-{\zeta }^j}=1$. When $n$ is even, we also have the term ${\prod }_{j\ne \frac{n}{2}}\frac{1+{\zeta }^j}{-1-{\zeta }^j}=(-1{)}^{n-1}=-1$, so the sum is 0 .

$$G\left(x_1,\dots ,x_n\right)=\frac{P\left(x_n\right)}{{\prod }_{j\ne n}\left(x_n-x_j\right)}$$ where $P\left(x_n\right)$ is a polynomial in $x_n$ whose coefficients are rational functions in the other variables. We then have $$P\left(x_n\right)=\left(\prod _{j\ne n}\left(1-x_n{x}_j\right)\right)+\sum _{1⩽i⩽n-1}\left(x_i{x}_n-1\right)\left(\prod _{j\ne i,n}\left(x_n-x_j\right)\right)\left(\prod _{j\ne i,n}\frac{1-x_i{x}_j}{x_i-x_j}\right).$$ For any $k\ne n$, substituting $x_n=x_k$ (which is valid when manipulating the numerator $P\left(x_n\right)$ on its own), we have (noting that $x_n-x_j$ vanishes when $j=k$ ) $$\begin{array}{rl}P\left(x_k\right)& =\left(\prod _{j\ne n}\left(1-x_k{x}_j\right)\right)+\sum _{1⩽i⩽n-1}\left(x_i{x}_k-1\right)\left(\prod _{j\ne i,n}\left(x_k-x_j\right)\right)\left(\prod _{j\ne i,n}\frac{1-x_i{x}_j}{x_i-x_j}\right)\\ & =\left(\prod _{j\ne n}\left(1-x_k{x}_j\right)\right)+\left(x_k^2-1\right)\left(\prod _{j\ne k,n}\left(x_k-x_j\right)\right)\left(\prod _{j\ne k,n}\frac{1-x_k{x}_j}{x_k-x_j}\right)\\ & =\left(\prod _{j\ne n}\left(1-x_k{x}_j\right)\right)+\left(x_k^2-1\right)\left(\prod _{j\ne k,n}\left(1-x_k{x}_j\right)\right)\\ & =0\end{array}$$ Note that $P$ is a polynomial in $x_n$ of degree $n-1$. For any choice of distinct real numbers $x_1,\dots ,x_{n-1},P$ has those real numbers as its roots, and the denominator has the same degree and the same roots. This shows that $G$ is constant in $x_n$, for any fixed choice of distinct $x_1,\dots ,x_{n-1}$. Now, $G$ is symmetric in all $n$ variables, so it must be also be constant in each of the other variables. $G$ is therefore a constant that depends only on $n$. The constant may be identified as in the previous solution.