Difference between revisions of "1985 IMO Problems/Problem 3"
Sudark2k22 (talk | contribs) |
Sudark2k22 (talk | contribs) |
||
(One intermediate revision by the same user not shown) | |||
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]] |
Latest revision as of 04:56, 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 |