Difference between revisions of "2006 IMO Problems/Problem 5"
(→Solution: grammar fixed) |
m (→Solution) |
||
Line 36: | Line 36: | ||
<cmath> (a_1-a_0) + (a_2-a_1) + \dotsb + (a_r-a_{r-1}) = a_r-a_0 = 0, </cmath> | <cmath> (a_1-a_0) + (a_2-a_1) + \dotsb + (a_r-a_{r-1}) = a_r-a_0 = 0, </cmath> | ||
it follows that for some index <math>j</math>, | it follows that for some index <math>j</math>, | ||
− | <cmath> a_j - a_{j+1} = -(a_{j+1} - a_{j+ | + | <cmath> a_j - a_{j+1} = -(a_{j+1} - a_{j+2}), </cmath> |
or <math>a_j = a_{j+2} = P^2(a_j)</math>. Since <math>a = a_r = P^{r-j}(a_j)</math>, it then follows that <math>P^2(a) = a</math>, as desired. <math>\blacksquare</math> | or <math>a_j = a_{j+2} = P^2(a_j)</math>. Since <math>a = a_r = P^{r-j}(a_j)</math>, it then follows that <math>P^2(a) = a</math>, as desired. <math>\blacksquare</math> | ||
Revision as of 14:21, 7 September 2021
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>