Maths Olympiad Prep

Library / /13 of 71

Combinatorics Difficulty 4.7 AIME Find the answer United States

Problem:
A monomial term xi1xi2xikx_{i_{1}} x_{i_{2}} \ldots x_{i_{k}} in the variables x1,x2,,x8x_{1}, x_{2}, \ldots, x_{8} is square-free if i1,i2,,iki_{1}, i_{2}, \ldots, i_{k} are distinct. (A constant term such as 11 is considered square-free.) What is the sum of the coefficients of the squarefree terms in the following product?
1i<j8(1+xixj) \prod_{1 \leq i<j \leq 8}\left(1+x_{i} x_{j}\right)

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
Answer: 764764
Let ana_{n} be the sum of the coefficients of the square-terms in the product 1i<jn(1+xixj)\prod_{1 \leq i<j \leq n}(1+ x_{i} x_{j}). Square-free terms in this product come in two types: either they include xnx_{n}, or they do not. The sum of the coefficients of the terms that include xnx_{n} is (n1)an2(n-1) a_{n-2}, since we can choose any of the n1n-1 other variables to be paired with xnx_{n}, and then choose any square-free term from the product taken over the other n2n-2 variables. The sum of the coefficients of the terms that do not include xnx_{n} are an1a_{n-1}, because they all come from the product over the other n1n-1 variables. Therefore, an=an1+(n1)an2a_{n}=a_{n-1}+(n-1) a_{n-2}.

We use this recursion to find a8a_{8}. As base cases, a0a_{0} and a1a_{1} are both 11. Then a2=2a_{2}=2, a3=4a_{3}=4, a4=10a_{4}=10, a5=26a_{5}=26, a6=76a_{6}=76, a7=232a_{7}=232, and finally, a8=764a_{8}=764.

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.