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