Mock AIME 4 2006-2007 Problems/Problem 3

Problem

Find the largest prime factor of the smallest positive integer $n$ such that $r_1, r_2, \ldots , r_{2006}$ are distinct integers such that the polynomial $(x-r_{1})(x-r_{2})\cdots (x-r_{2006})$ has exactly $n$ nonzero coefficients.

The following solution is non-rigorous.

We would normally expect 2007 terms after multiplying out all of the binomials, but our goal is minimize the number of non-zero terms. We could get rid of some terms by applying repeated difference of squares. In other words, we let $r_1 = -r_2, \ldots, r_{2005} = -r_{2006}$ . Then our polynomial reduces to $(x^2 - r_1^2)(x^2 - r_3^2)\cdots (x^2 - r_{2005}^2)$ . This is the product of $1003$ binomials, which gives us $1004$ terms (with nonzero coefficients). Since $1004 = 2^2 \cdot 251$ (assuming the constant term counts as a coefficient), our answer is $251$ .

Note that we could not apply difference of cubes etc, since that would require complex roots.