IMO Shortlist, 2019

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 \neq i} 1-x_{i} x_{j}$$
Using the nodes $+1,-1, x_{1}, \ldots, 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 \neq i} \frac{x-x_{j}}{x_{i}-x_{j}}+f(1) \frac{x+1}{1+1} \prod_{1 \leqslant i \leqslant n} \frac{x-x_{i}}{1-x_{i}}+f(-1) \frac{x-1}{-1-1} \prod_{1 \leqslant i \leqslant 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{aligned} 0 & =\sum_{1 \leqslant i \leqslant n} \frac{f\left(x_{i}\right)}{\prod_{j \neq i}\left(x_{i}-x_{j}\right) \cdot\left(x_{i}-1\right)\left(x_{i}+1\right)}+\frac{f(1)}{\prod_{1 \leqslant j \leqslant n}\left(1-x_{j}\right) \cdot(1+1)}+\frac{f(-1)}{\prod_{1 \leqslant j \leqslant n}\left(-1-x_{j}\right) \cdot(-1-1)} \\ & =-G\left(x_{1}, \ldots, x_{n}\right)+\frac{1}{2}+\frac{(-1)^{n+1}}{2} \end{aligned}$$

Solution 2 (using symmetries). Observe that $G$ is symmetric in the variables $x_{1}, \ldots, 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}, \ldots, 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}, \ldots, x_{n}$ vanishes when any two variables $x_{i}, x_{j}(i \neq j)$ are equal, and is therefore divisible by $x_{i}-x_{j}$ for each pair $i \neq 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}, \ldots, x_{n}$.
Now observe that if all $x_{i}$ are nonzero and we set $y_{i}=1 / x_{i}$ for $i=1, \ldots, 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}}, \ldots, \frac{1}{x_{n}}\right)=G\left(x_{1}, \ldots, 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}, \ldots, c_{n}\right)$ with all $c_{i} \neq 0$, such that $G\left(c_{1}, \ldots, c_{n}\right) \neq G(0, \ldots, 0)$; then $g(x):=G\left(c_{1} x, \ldots, c_{n} x\right)$ would be a nonconstant polynomial in the variable $x$, so $|g(x)| \rightarrow \infty$ as $x \rightarrow \infty$, hence $\left|G\left(\frac{y}{c_{1}}, \ldots, \frac{y}{c_{n}}\right)\right| \rightarrow \infty$ as $y \rightarrow 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 $2 i=n$. In the case where $n$ is odd, the only exceptional term is $i=n$, which gives the value $\prod_{j \neq n} \frac{1-\zeta^{j}}{1-\zeta^{j}}=1$. When $n$ is even, we also have the term $\prod_{j \neq \frac{n}{2}} \frac{1+\zeta^{j}}{-1-\zeta^{j}}=(-1)^{n-1}=-1$, so the sum is 0 .

$$G\left(x_{1}, \ldots, x_{n}\right)=\frac{P\left(x_{n}\right)}{\prod_{j \neq 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 \neq n}\left(1-x_{n} x_{j}\right)\right)+\sum_{1 \leqslant i \leqslant n-1}\left(x_{i} x_{n}-1\right)\left(\prod_{j \neq i, n}\left(x_{n}-x_{j}\right)\right)\left(\prod_{j \neq i, n} \frac{1-x_{i} x_{j}}{x_{i}-x_{j}}\right) .$$
For any $k \neq 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{aligned} P\left(x_{k}\right) & =\left(\prod_{j \neq n}\left(1-x_{k} x_{j}\right)\right)+\sum_{1 \leqslant i \leqslant n-1}\left(x_{i} x_{k}-1\right)\left(\prod_{j \neq i, n}\left(x_{k}-x_{j}\right)\right)\left(\prod_{j \neq i, n} \frac{1-x_{i} x_{j}}{x_{i}-x_{j}}\right) \\ & =\left(\prod_{j \neq n}\left(1-x_{k} x_{j}\right)\right)+\left(x_{k}^{2}-1\right)\left(\prod_{j \neq k, n}\left(x_{k}-x_{j}\right)\right)\left(\prod_{j \neq k, n} \frac{1-x_{k} x_{j}}{x_{k}-x_{j}}\right) \\ & =\left(\prod_{j \neq n}\left(1-x_{k} x_{j}\right)\right)+\left(x_{k}^{2}-1\right)\left(\prod_{j \neq k, n}\left(1-x_{k} x_{j}\right)\right) \\ & =0 \end{aligned}$$
Note that $P$ is a polynomial in $x_{n}$ of degree $n-1$. For any choice of distinct real numbers $x_{1}, \ldots, 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}, \ldots, 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.