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"

m
(hope I did this right.. + sol)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
 +
:''The following solution is non-rigorous''.
  
−
{{solution}}
+
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.
  
−
----
+
==See also==
 +
{{Mock AIME box|year=2006-2007|n=4|num-b=2|num-a=4|source=125025}}
  
−
*[[Mock AIME 4 2006-2007 Problems/Problem 4| Next Problem]]
+
[[Category:Intermediate Algebra Problems]]
−
*[[Mock AIME 4 2006-2007 Problems/Problem 2| Previous Problem]]
 
−
*[[Mock AIME 4 2006-2007 Problems]]
 

Revision as of 15:41, 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=17609"