Problem 1807

1. Define the function and polynomial:
We start by defining the function $f_n(x_1, \ldots, x_n)$ and the polynomial $P_n(x_1, \ldots, x_n)$ as follows:
$$f_n(x_1, \ldots, x_n) := \sum_{1 \le i \le n} \prod_{j \neq i} \frac{1 - x_i x_j}{x_i - x_j} =: \frac{P_n(x_1, \ldots, x_n)}{\prod_{i < j} (x_i - x_j)}.$$
Here, $f_n$ is the function in the problem, and $P_n$ is the polynomial obtained by multiplying through by the common denominator $\prod_{i < j} (x_i - x_j)$.

2. Claim 1:
For all $1 \le i \le n$, we have:
$$x_i - 1 \mid P_n(x_1, \ldots, x_n) - (n \mod 2) \prod_{i < j} (x_i - x_j).$$
Proof:
We will show $x_n - 1 \mid P_n$, which suffices by symmetry. Let $g(x_1, \ldots, x_n) = f_n(x_1, \ldots, x_n) - (n \mod 2)$. Then essentially the claim is saying that $x_i - 1 \mid g_n(x_1, \ldots, x_n)$. Plugging $x_n = 1$, we see:
$$f(x_1, \ldots, x_{n-1}, 1) = 1 + \sum_{1 \le i \le n-1} \frac{1 - x_i}{x_i - 1} \prod_{\substack{j \neq i \\ j \neq n}} \frac{1 - x_i x_j}{x_i - x_j} = 1 - f_{n-1}(x_1, \ldots, x_{n-1}).$$
By induction on the original problem statement, $f_{n-1}(x_1, \ldots, x_{n-1}) = (n-1 \mod 2)$. Hence by the above, $f(x_1, \ldots, x_{n-1}, 1) = (n \mod 2)$, i.e., $g(x_1, \ldots, x_{n-1}, 1) = 0$. Treating $g(x_1, \ldots, x_n)$ as a polynomial in $x_n$, this proves $x_n - 1 \mid g(x_1, \ldots, x_n)$, as needed. $\blacksquare$

3. Claim 2:
For all $1 \le i < j \le n$, we have $x_i - x_j \mid P_n(x_1, \ldots, x_n)$.

Proof:
Fix $a < b$, and assume $x_a = x_b$. We will prove $P_n(x_1, \ldots, x_n) = 0$. We have:
$$f_n(x_1, \ldots, x_n) = \sum_{1 \le i \le n} S_i(x_1, \ldots, x_n),$$
where the summand $S_i$ is:
$$S_i(x_1, \ldots, x_n) = \frac{(1 - x_i x_1) \cdots (1 - x_i x_{i-1})(1 - x_i x_{i+1}) \cdots (1 - x_i x_n)}{(x_i - x_1) \cdots (x_i - x_{i-1})(x_i - x_{i+1}) \cdots (x_i - x_n)}.$$
For a fixed $k$, when we multiply $S_k$ through by $\prod_{i < j} (x_i - x_j)$, we get a product, and this product contains all terms of the form $(x_i - x_j)$, where $i \neq k$. In particular, $S_k$ for $k \notin \{a, b\}$ is a product which contains $x_a - x_b$ (or its negative), and hence $S_k = 0$ for $k \notin \{a, b\}$. So actually $f_n = S_a + S_b$, so:
$$P_n = S_a \prod_{i < j} (x_i - x_j) + S_b \prod_{i < j} (x_i - x_j).$$
We see that:
$$S_a \prod_{i < j} (x_i - x_j) = \left( \prod_{i \neq a} (1 - x_a x_i) \right) \cdot \left( (-1)^{a-1} \prod_{i < j, i, j \neq a} (x_i - x_j) \right),$$
$$S_b \prod_{i < j} (x_i - x_j) = \left( \prod_{i \neq b} (1 - x_b x_i) \right) \cdot \left( (-1)^{b-1} \prod_{i < j, i, j \neq b} (x_i - x_j) \right).$$
where the $(-1)^{a-1}$ comes due to the fact that when we multiply $\prod (x_i - x_j)$, the terms $x_a - x_1, \ldots, x_a - x_{a-1}$ need to be switched in sign.

We claim that on the RHS, the first terms are equal and the second terms are negatives. For the first terms, note that since $x_a = x_b$:
$$\prod_{i \neq a} (1 - x_a x_i) = \frac{\prod_{i} (1 - x_a x_i)}{1 - x_a^2} = \frac{\prod_{i} (1 - x_b x_i)}{1 - x_b^2} = \prod_{i \neq b} (1 - x_b x_i),$$
as needed. For the second terms, we want to show:
$$(-1)^{a-1} \prod_{i < j, i, j \neq a} (x_i - x_j) = - (-1)^{b-1} \prod_{i < j, i, j \neq b} (x_i - x_j).$$
It suffices to show the "complement"; however, we have to remove $x_a - x_b$ since it is equal to $0$. We want to show:
$$(-1)^{a-1} \prod_{\substack{i < j \\ a \in \{i, j\} \\ (i, j) \neq (a, b)}} (x_i - x_j) = -(-1)^{b-1} \prod_{\substack{i < j \\ b \in \{i, j\} \\ (i, j) \neq (a, b)}} (x_i - x_j).$$
Writing out the LHS and RHS above (omitting the $(-1)$ powers):
$$(x_a - x_{a+1}) \cdots (x_a - x_{b-1}) \underbrace{(x_a - x_{b+1}) \cdots (x_a - x_n)}_{(\spadesuit)} \underbrace{(x_1 - x_a) \cdots (x_{a-1} - x_a)}_{(\heartsuit)},$$
$$\underbrace{(x_b - x_{b+1}) \cdots (x_b - x_n)}_{(\spadesuit)} \underbrace{(x_1 - x_b) \cdots (x_{a-1} - x_b)}_{(\heartsuit)} (x_{a+1} - x_b) \cdots (x_{b-1} - x_b).$$
The corresponding sets of terms are underlined under common $(\heartsuit)$ and $(\spadesuit)$ braces. The remaining terms can be paired up in pairs that are negatives of each other. Since there are $b - a - 1$ such pairs, the quotient of the LHS and RHS is $(-1)^{b - a - 1}$. This proves the desired. $\blacksquare$

4. Conclusion:
From Claim 2, we know:
$$\prod_{i < j} (x_i - x_j) \mid P_n(x_1, \ldots, x_n).$$
Hence $f_n(x_1, \ldots, x_n)$ is actually a polynomial, not just a rational function. Now, Claim 1 implies that:
$$(x_1 - 1) \cdots (x_n - 1) \mid f_n(x_1, \ldots, x_n) - (n \mod 2).$$
But $\deg f_n(x_1, \ldots, x_n) = n - 1$. Even with multiple variables, it is impossible for a degree $n$ polynomial to divide a nonzero degree $n - 1$ polynomial. Therefore, $f_n(x_1, \ldots, x_n) = (n \mod 2)$.

$\blacksquare$