Difference between revisions of "1985 IMO Problems/Problem 3"
(template) |
Sudark2k22 (talk | contribs) |
||
Line 35: | Line 35: | ||
{{IMO box|year=1985|num-b=2|num-a=4}} | {{IMO box|year=1985|num-b=2|num-a=4}} | ||
− | [[Category:Olympiad Algebra Problems]] | + | [[Category:Olympiad Algebra Problems]]Suuuuuuuuuuuuuuuuuuuuuu |
Revision as of 03:55, 11 March 2023
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 |
Suuuuuuuuuuuuuuuuuuuuuu