On the board, $(n-1) n$ expressions are written: $x_{1}-x_{2}, x_{1}-x_{3}, \ldots, x_{1}-x_{n}, x_{2}-x_{1}, x_{2}-x_{3}, \ldots, x_{2}-x_{n}, \ldots, x_{n}-x_{n-1}$, where $n \geq 3$. Lёsha wrote down all these expressions in his notebook, their sums of two different ones, of three different ones, and so on, up to the sum of all expressions. In all the sums he wrote down, Lёsha combined like terms (for example, instead of $\left(x_{1}-x_{2}\right)+\left(x_{2}-x_{3}\right)$, Lёsha would write $x_{1}-x_{3}$, and instead of $\left(x_{1}-x_{2}\right)+\left(x_{2}-x_{1}\right)$, he would write 0).

How many expressions did Lёsha write in his notebook exactly once?
All differences written on the board are paired into opposite pairs: $\left\{x_{i}-x_{j}, x_{j}-x_{i}\right\}$. If some sum (before combining like terms) does not contain either the difference $x_{i}-x_{j}$ or the difference $x_{j}-x_{i}$, then we can add $\left(x_{i}-x_{j}\right)+\left(x_{j}-x_{i}\right)$ to this sum and obtain a sum equal to the original. If some sum contains both the term $x_{i}-x_{j}$ and the term $x_{j}-x_{i}$, then we can erase them and again obtain a sum equal to the original. Therefore, in each sum written in the notebook exactly once, from each pair of opposite differences, exactly one is present.

For each such sum $S$, we define a (linear) order on the set $\left\{x_{1}, \ldots, x_{n}\right\}$ by setting $x_{i}>$ $x_{j}$ if the term $x_{i}-x_{j}$ is included in $S$. We need to check that this relation is transitive (if $x_{i}>x_{j}$ and $x_{j}>x_{k}$, then $\left.x_{i}>x_{k}\right)$. Indeed, in $S$, the terms $x_{i}-x_{j}$, $x_{j}-x_{k}$, and $x_{k}-x_{i}$ cannot all be present simultaneously, since their sum is zero.

Conversely, for each order relation, we can reconstruct the corresponding sum. We need to prove that it will appear in the notebook only once. By symmetry, it is sufficient to check this for the order $x_{1}j$. Any other sum written by Alex, before fully combining like terms, can be written as a sum of the same expressions with coefficients 0 and $\pm 1$. Substitute the values $x_{1}=1, x_{2}=2, \ldots, x_{n}=n$ into both sums. In $S$, all terms will become positive, while in the second sum, some terms will be missing or negative. The values of the sums are different, so they cannot coincide after combining like terms.

Therefore, the number of sums is equal to the number of ways to define an order on a set of $n$ elements. This number is obviously equal to the number of permutations of $n$ elements, which is $n!$.

## Answer

$n!$ expressions.

Submit a comment