2006 IMO Problems/Problem 5
Problem
(Dan Schwarz, Romania)
Let be a polynomial of degree
with integer coefficients, and let
be a positive integer. Consider the polynomial
, where
occurs
times. Prove that there are at most
integers
such that
.
Solution
We use the notation for
.
Lemma 1. The problem statement holds for .
Proof. Suppose that ,
are integers such that
and
for all indices
. Let the set
have
distinct elements. It suffices to show that
.
If for all indices
, then the polynomial
has at least
roots; since
is not linear, it follows that
by the division algorithm.
Suppose on the other hand that , for some index
. In this case, we claim that
is constant for every index
. Indeed, we note that
so
. Similarly,
so
. It follows that
.
This proves our claim. It follows that the polynomial
has at least
roots. Since
is not linear it follows again that
, as desired. Thus the lemma is proven.
Lemma 2. If is a positive integer such that
for some positive integer
, then
.
Proof. Let us denote , and
, for positive integers
. Then
, and
It follows that
is constant for all indices
; let us abbreviate this quantity
. Now, since
it follows that for some index
,
or
. Since
, it then follows that
, as desired.
Now, if there are more than integers
for which
, then by Lemma 2, there are more than
integers
such that
, which is a contradiction by Lemma 1. Thus the problem is solved.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
Resources
- 1974 USAMO Problems/Problem 1, which implies a special case of this problem
2006 IMO (Problems) • Resources | ||
Preceded by Problem 4 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 6 |
All IMO Problems and Solutions |
- <url>Forum/viewtopic.php?p=572821#p572821 Discussion on AoPS/MathLinks</url>