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 "1985 IMO Problems/Problem 3"

 
(template)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
  
−
For any polynomial <math> P(x) = a_0 + a_1 x + \cdots + a_k x^k </math> with integer coefficients, the number of coefficients which are odd is denoted by <math> \displaystyle w(P) </math>.  For <math> i = 0, 1, \ldots </math>, let <math> \displaystyle Q_i (x) = (1+x)^i </math>.  Prove that if <math> i_1, i_2, \ldots , i_n </math> are integers such that <math> 0 \leq i_1 < i_2 < \cdots < i_n </math>, then
+
For any polynomial <math> P(x) = a_0 + a_1 x + \cdots + a_k x^k </math> with integer coefficients, the number of coefficients which are odd is denoted by <math>w(P) </math>.  For <math> i = 0, 1, \ldots </math>, let <math>Q_i (x) = (1+x)^i </math>.  Prove that if <math> i_1, i_2, \ldots , i_n </math> are integers such that <math> 0 \leq i_1 < i_2 < \cdots < i_n </math>, then
  
 
<center>
 
<center>
 
<math>
 
<math>
−
\displaystyle w(Q_{i_1} + Q_{i_2} + \cdots + Q_{i_n}) \ge w(Q_{i_1})
+
w(Q_{i_1} + Q_{i_2} + \cdots + Q_{i_n}) \ge w(Q_{i_1})
 
</math>.
 
</math>.
 
</center>
 
</center>
Line 11: Line 11:
 
== Solution ==
 
== Solution ==
  
−
We first observe that <math>(1+x)^{2^m} \equiv 1 + x^{2^m} \pmod{2}</math>, so for any polynomial <math>\displaystyle P</math> of degree less than <math> \displaystyle 2^m </math>, <math> w(P\cdot Q_{2^m}) = 2w (P)</math>.  
+
We first observe that <math>(1+x)^{2^m} \equiv 1 + x^{2^m} \pmod{2}</math>, so for any polynomial <math>P</math> of degree less than <math>2^m </math>, <math> w(P\cdot Q_{2^m}) = 2w (P)</math>.  
  
−
Let <math>\displaystyle k</math> be the largest power of 2 that is less than or equal to <math>\displaystyle i_n</math>.  We proceed by induction on <math>\displaystyle k</math>.
+
Let <math>k</math> be the largest power of 2 that is less than or equal to <math>i_n</math>.  We proceed by induction on <math>k</math>.
  
−
For <math>\displaystyle k = 0</math>, the problem is trivial.
+
For <math>k = 0</math>, the problem is trivial.
  
−
Now assume that the problem holds for <math>\displaystyle k-1</math>.  We now have two cases: <math> i_1 \ge k</math>, and <math>\displaystyle i_1 < k</math>.
+
Now assume that the problem holds for <math>k-1</math>.  We now have two cases: <math> i_1 \ge k</math>, and <math>i_1 < k</math>.
  
 
In the first case, we note that <math> w \left( \sum_{j=1}^{n}Q_{i_j} \right) = w \left( (1+x)^k \sum_{j=1}^{n}Q_{i_j - k} \right) = 2 w \left( \sum_{j=1}^{n}Q_{i_j - k} \right)</math>, which is greater than or equal to <math> w( Q_{i_1} )</math> by assumption.
 
In the first case, we note that <math> w \left( \sum_{j=1}^{n}Q_{i_j} \right) = w \left( (1+x)^k \sum_{j=1}^{n}Q_{i_j - k} \right) = 2 w \left( \sum_{j=1}^{n}Q_{i_j - k} \right)</math>, which is greater than or equal to <math> w( Q_{i_1} )</math> by assumption.
Line 29: Line 29:
 
</center>
 
</center>
  
−
But by assumption, <math> w \left( \sum_{j=0}^{k-1}a_j x^j \right) \ge w( Q_{i_1})</math>, and for each odd <math> \displaystyle a_j </math>, at least one of <math> \displaystyle (a_j + b_j ) </math> and <math> \displaystyle b_j </math> must be odd, Q.E.D.
+
But by assumption, <math> w \left( \sum_{j=0}^{k-1}a_j x^j \right) \ge w( Q_{i_1})</math>, and for each odd <math>a_j </math>, at least one of <math>(a_j + b_j ) </math> and <math>b_j </math> must be odd, Q.E.D.
  
  
 
{{alternate solutions}}
 
{{alternate solutions}}
−
 
+
{{IMO box|year=1985|num-b=2|num-a=4}}
−
== Resources ==
 
−
 
 
−
* [[1985 IMO Problems]]
 
−
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366592#p366592 Discussion on AoPS/MathLinks]
 
−
 
 
  
 
[[Category:Olympiad Algebra Problems]]
 
[[Category:Olympiad Algebra Problems]]

Revision as of 19:55, 25 October 2007

Problem

For any polynomial $P(x) = a_0 + a_1 x + \cdots + a_k x^k$ with integer coefficients, the number of coefficients which are odd is denoted by $w(P)$. For $i = 0, 1, \ldots$, let $Q_i (x) = (1+x)^i$. Prove that if $i_1, i_2, \ldots , i_n$ are integers such that $0 \leq i_1 < i_2 < \cdots < i_n$, then

$w(Q_{i_1} + Q_{i_2} + \cdots + Q_{i_n}) \ge w(Q_{i_1})$.

Solution

We first observe that $(1+x)^{2^m} \equiv 1 + x^{2^m} \pmod{2}$, so for any polynomial $P$ of degree less than $2^m$, $w(P\cdot Q_{2^m}) = 2w (P)$.

Let $k$ be the largest power of 2 that is less than or equal to $i_n$. We proceed by induction on $k$.

For $k = 0$, the problem is trivial.

Now assume that the problem holds for $k-1$. We now have two cases: $i_1 \ge k$, and $i_1 < k$.

In the first case, we note that $w \left( \sum_{j=1}^{n}Q_{i_j} \right) = w \left( (1+x)^k \sum_{j=1}^{n}Q_{i_j - k} \right) = 2 w \left( \sum_{j=1}^{n}Q_{i_j - k} \right)$, which is greater than or equal to $w( Q_{i_1} )$ by assumption.

In the second case, we use the division algorithm to note that

$\sum_{j=1}^{n}Q_{i_j} = \sum_{j=0}^{k-1}a_j x^j + (1+x)^k \sum_{j=0}^{k-1} b_j x^j \equiv \sum_{j=0}^{k-1}\left[ (a_j + b_j)x^j + b_j x^{j+k} \right] \pmod{2}$.

But by assumption, $w \left( \sum_{j=0}^{k-1}a_j x^j \right) \ge w( Q_{i_1})$, and for each odd $a_j$, at least one of $(a_j + b_j )$ and $b_j$ must be odd, Q.E.D.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

1985 IMO (Problems) • Resources
Preceded by
Problem 2 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 4
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1985_IMO_Problems/Problem_3&oldid=18788"