Library / /45 of 68

, 2017

Algebra Difficulty 5.6 AIME, harder Prove it United States

Problem:
Find (in terms of $n \geq 1$ ) the number of terms with odd coefficients after expanding the product:
$\prod_{1 \leq i<j \leq n}\left(x_{i}+x_{j}\right)$
e.g., for $n=3$ the expanded product is given by $x_{1}^{2} x_{2}+x_{1}^{2} x_{3}+x_{2}^{2} x_{3}+x_{2}^{2} x_{1}+x_{3}^{2} x_{1}+x_{3}^{2} x_{2}+2 x_{1} x_{2} x_{3}$ and so the answer would be 6.

Solution

Solution:
Note that if we take $(\bmod\ 2)$ , we get that
$\prod_{1 \leq i<j \leq n}\left(x_{i}+x_{j}\right) \equiv \prod_{1 \leq i<j \leq n}\left(x_{j}-x_{i}\right)=\operatorname{det}(M)$
where $M$ is the matrix with $M_{ij}=x_{i}^{j-1}$ . This is called a Vandermonde determinant. Expanding this determinant using the formula
$\operatorname{det}(M)=\sum_{\sigma} \prod_{i=1}^{n} x_{\sigma(i)}^{i-1},$
where the sum is over all $n!$ permutations $\sigma$ , gives the result.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.