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> | + | 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> | ||
− | + | 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> | + | 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> | + | 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> | + | For <math>k = 0</math>, the problem is trivial. |
− | Now assume that the problem holds for <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> | + | 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}} | |
− | |||
− | |||
− | |||
− | |||
− | |||
[[Category:Olympiad Algebra Problems]] | [[Category:Olympiad Algebra Problems]] |
Latest revision as of 20:55, 25 October 2007
Problem
For any polynomial with integer coefficients, the number of coefficients which are odd is denoted by . For , let . Prove that if are integers such that , then
.
Solution
We first observe that , so for any polynomial of degree less than , .
Let be the largest power of 2 that is less than or equal to . We proceed by induction on .
For , the problem is trivial.
Now assume that the problem holds for . We now have two cases: , and .
In the first case, we note that , which is greater than or equal to by assumption.
In the second case, we use the division algorithm to note that
.
But by assumption, , and for each odd , at least one of and 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 |