Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Mock AIME 4 2006-2007 Problems/Problem 3"

(hope I did this right.. + sol)
m (→‎Solution: {})
 
Line 5: Line 5:
 
:''The following solution is non-rigorous''.
 
:''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 <math>r_1 = -r_2, \ldots, r_2005 = -r_2006</math>. Then our polynomial reduces to <math>(x^2 - r_1^2)(x^2 - r_3^2)\cdots (x^2 - r_{2005}^2)</math>. This is the product of <math>1003</math> binomials, which gives us <math>1004</math> terms (with nonzero coefficients). Since <math>1004 = 2^2 \cdot 251</math> (assuming the constant term counts as a coefficient), our answer is <math>251</math>.   
+
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 <math>r_1 = -r_2, \ldots, r_{2005} = -r_{2006}</math>. Then our polynomial reduces to <math>(x^2 - r_1^2)(x^2 - r_3^2)\cdots (x^2 - r_{2005}^2)</math>. This is the product of <math>1003</math> binomials, which gives us <math>1004</math> terms (with nonzero coefficients). Since <math>1004 = 2^2 \cdot 251</math> (assuming the constant term counts as a coefficient), our answer is <math>251</math>.   
  
 
Note that we could not apply difference of cubes etc, since that would require complex roots.
 
Note that we could not apply difference of cubes etc, since that would require complex roots.

Latest revision as of 14:44, 8 October 2007

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.

Solution

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.

See also

Mock AIME 4 2006-2007 (Problems, Source)
Preceded by
Problem 2 		Followed by
Problem 4
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_4_2006-2007_Problems/Problem_3&oldid=17610"