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