2006 IMO Problems/Problem 5
(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 .
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.
- 1974 USAMO Problems/Problem 1, which implies a special case of this problem
|2006 IMO (Problems) • Resources|
|1 • 2 • 3 • 4 • 5 • 6||Followed by|
|All IMO Problems and Solutions|
- <url>Forum/viewtopic.php?p=572821#p572821 Discussion on AoPS/MathLinks</url>