Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2006 IMO Problems/Problem 5"

(→‎Hint)
m (→‎Solution 2)
 
(4 intermediate revisions by the same user not shown)
Line 43: Line 43:
  
 
{{alternate solutions}}
 
{{alternate solutions}}
−
== Hint ==
+
== Hints ==
 
Try to use contradiction:
 
Try to use contradiction:
 
Q(<math>x_1</math>)=<math>x_1</math>,<math>...</math>,Q(<math>x_{n+1}</math>)=<math>x_{n+1}</math>. WLOG suppose <math>x_1<...<x_{n+1}</math>.
 
Q(<math>x_1</math>)=<math>x_1</math>,<math>...</math>,Q(<math>x_{n+1}</math>)=<math>x_{n+1}</math>. WLOG suppose <math>x_1<...<x_{n+1}</math>.
Line 55: Line 55:
 
Construct a polynomial to give the final contradiction by keeping in mind the theorem:
 
Construct a polynomial to give the final contradiction by keeping in mind the theorem:
 
If the equation f(x)=<math>a</math> (<math>a</math> is a constant)has more roots than deg(f), then f=a.
 
If the equation f(x)=<math>a</math> (<math>a</math> is a constant)has more roots than deg(f), then f=a.
 +
 +
== Solution 2 ==
 +
 +
Note:
 +
We will denote <math> P(...(P(x))....) </math> (where <math>P</math> occurs <math>k</math> times) as <math>P_k(x)</math> throughout the proof, for any integer <math>k>1</math>.
 +
 +
For the sake of contradiction, let the problem statement be false.
 +
For convinience's sake, let the stated equation have <math>n+1</math> solutions:
 +
<math> P_k(x_1)</math> = <math>x_1</math>,...,<math>P_k(x_{n+1})</math> = <math>x_{n+1}</math>.
 +
 +
Without loss of generality, suppose <math>x_1 < ... <x_{n+1}</math>.
 +
 +
As P is defined over the integers, <math>x_i - x_j \mid P(x_i) - P(x_j)</math>.
 +
Also, <math>P(x_i) - P(x_j) \mid P_2(x_i) - P_2(x_j) \mid ... \mid P_k(x_i) - P_k(x_j) = x_i - x_j.</math>
 +
Hence, <math>|P(x_i) - P(x_j)| = x_i - x_j</math> for all <math>i<j</math>.
 +
 +
Claim.
 +
 +
<math>P(x_i) \neq P(x_j)</math> for any <math>i \neq j</math>.
 +
 +
Proof.
 +
 +
For the sake of contradiction, suppose the claim statement is wrong.
 +
Without loss of generality, suppose <math>i>j</math>.
 +
 +
Then, <math>P(x_i)=P(x_j) => P(x_i)-P(x_j)=0 => |P(x_i)-P(x_j)|=0 => x_i - x_j = 0 => x_i=x_j</math>, a contradiction.
 +
 +
Hence, our claim is proved.
 +
 +
 +
Claim.
 +
 +
<math>P(x_1),...,P(x_{n+1})</math> is either increasing or decreasing.
 +
 +
Proof.
 +
 +
We will only prove the increasing part, as the decreasing part is similar.
 +
 +
For the sake of contradiction, suppose the claim statement is wrong.
 +
Then, <math>P(x_{i-1})>P(x_i)</math> and <math>P(x_i)<P(x_{i+1})</math> for some integer <math>i>1</math>.
 +
 +
For convinience's sake, suppose <math>i=2</math>.
 +
 +
Then, <math>|P(x_1)-P(x_2)|=P(x_1)-P(x_2)=x_2-x_1</math> and <math>|P(x_3)-P(x_2)|=P(x_3)-P(x_2)=x_3-x_2</math>.
 +
 +
Adding, we get that <math>(P(x_1)+P(x_3))-2 \cdot P(x_2) = x_3 - x_1</math>.
 +
 +
Now, <math>x_3 - x_1</math> will either be substituted by <math>P(x_1)-P(x_3)</math> or <math>P(x_3)-P(x_1)</math>.
 +
 +
Either way, we get a contradiction to our previous claim.
 +
 +
Hence, <math>P(x_2)>P(x_3)</math>.
 +
Similarly, <math>P(x_3)>P(x_4)</math>,...,<math>P(x_n)>P(x_{n+1})</math>.
 +
 +
Then, <math>P(x_1)>...>P(x_{n+1})</math>.
 +
 +
One may similarly show the decreasing part.
 +
 +
Hence, our claim is proved.
 +
 +
 +
Case 1, The sequence <math>P(x_1),...,P(x_{n+1})</math> is decreasing:
 +
 +
Let <math>T(x)=(P(x)-x)-(P(x_1)-x_1)</math>.
 +
 +
Then, <math>T(x)</math> has <math>n+1</math> roots: <math>x_1,...,x_{n+1}</math>, while <math>deg(T)=deg(P)=n</math>, a contradiction.
 +
 +
One may similarly show the contradiction if the sequence <math>P(x_1),...,P(x_{n+1})</math> is increasing.
 +
 +
 +
Hence, we get our desired contradiction, and thus we are done.
  
 
== Resources ==
 
== Resources ==

Latest revision as of 05:41, 1 October 2025

Problem

(Dan Schwarz, Romania) Let $P(x)$ be a polynomial of degree $n>1$ with integer coefficients, and let $k$ be a positive integer. Consider the polynomial $Q(x) = P( P ( \ldots P(P(x)) \ldots ))$, where $P$ occurs $k$ times. Prove that there are at most $n$ integers $t$ such that $Q(t)=t$.

Solution

We use the notation $P^k(x)$ for $Q(x)$.

Lemma 1. The problem statement holds for $k=2$.

Proof. Suppose that $a_1, \dotsc, a_k$, $b_1, \dotsc, b_k$ are integers such that $P(a_j) = b_j$ and $P(b_j) = a_j$ for all indices $j$. Let the set $\{ a_1, \dotsc, a_k, b_1, \dotsc, b_k \}$ have $m$ distinct elements. It suffices to show that $\deg (P) \ge m$.

If $a_j = b_j$ for all indices $j$, then the polynomial $P(x)-x$ has at least $m$ roots; since $P$ is not linear, it follows that $\deg P \ge m$ by the division algorithm.

Suppose on the other hand that $a_i \neq b_i$, for some index $i$. In this case, we claim that $a_j + b_j$ is constant for every index $j$. Indeed, we note that \[a_j - a_i \mid P(a_j) - P(a_i) = b_j - b_i \mid P(b_j) - P(b_i) = a_j - a_i ,\] so $\lvert a_j - a_i \rvert = \lvert b_j - b_i \rvert$. Similarly, \[a_j - b_i \mid P(a_j) - P(b_i) = b_j - a_i \mid P(b_j) - P(a_i) = a_j - b_i,\] so $\lvert a_j - b_i \rvert = \lvert b_j - a_i \rvert$. It follows that $a_j + b_j = a_i + b_i$.

This proves our claim. It follows that the polynomial \[P(x) - \left( a_i + b_i - x \right)\] has at least $m$ roots. Since $P$ is not linear it follows again that $\deg P \ge m$, as desired. Thus the lemma is proven. $\blacksquare$

Lemma 2. If $a$ is a positive integer such that $P^r(a)$ for some positive integer $r$, then $P^2(a) = a$.

Proof. Let us denote $a_0 = a$, and $a_j = P^j(a)$, for positive integers $j$. Then $a_0 = a_r$, and \begin{align*} a_1 - a_0 &\mid P(a_1)- P(a_0) = a_2-a_1 \\ &\mid P(a_2) - P(a_1) = a_3 - a_2 \\ &\vdots \\ &\mid P(a_r)- P(a_{r-1}) = a_1 - a_0 . \end{align*} It follows that $\lvert a_{j+1} - a_j \rvert$ is constant for all indices $j$; let us abbreviate this quantity $d$. Now, since \[(a_1-a_0) + (a_2-a_1) + \dotsb + (a_r-a_{r-1}) = a_r-a_0 = 0,\] it follows that for some index $j$, \[a_j - a_{j+1} = -(a_{j+1} - a_{j+2}),\] or $a_j = a_{j+2} = P^2(a_j)$. Since $a = a_r = P^{r-j}(a_j)$, it then follows that $P^2(a) = a$, as desired. $\blacksquare$

Now, if there are more than $n$ integers $t$ for which $Q(t) = t$, then by Lemma 2, there are more than $n$ integers $t$ such that $P^2(t) = t$, which is a contradiction by Lemma 1. Thus the problem is solved. $\blacksquare$


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Hints

Try to use contradiction: Q($x_1$)=$x_1$,$...$,Q($x_{n+1}$)=$x_{n+1}$. WLOG suppose $x_1<...<x_{n+1}$.

Think of using the theorem $a-b \mid f(a)-f(b)$.

You will slowly get that |P($x_i$)-P($x_j$)|= $x_i-x_j$ (i<j).

Try to prove that P($x_1$),...,P($x_{n+1}$) is either increasing or decreasing.

Construct a polynomial to give the final contradiction by keeping in mind the theorem: If the equation f(x)=$a$ ($a$ is a constant)has more roots than deg(f), then f=a.

Solution 2

Note: We will denote $P(...(P(x))....)$ (where $P$ occurs $k$ times) as $P_k(x)$ throughout the proof, for any integer $k>1$.

For the sake of contradiction, let the problem statement be false. For convinience's sake, let the stated equation have $n+1$ solutions: $P_k(x_1)$ = $x_1$,...,$P_k(x_{n+1})$ = $x_{n+1}$.

Without loss of generality, suppose $x_1 < ... <x_{n+1}$.

As P is defined over the integers, $x_i - x_j \mid P(x_i) - P(x_j)$. Also, $P(x_i) - P(x_j) \mid P_2(x_i) - P_2(x_j) \mid ... \mid P_k(x_i) - P_k(x_j) = x_i - x_j.$ Hence, $|P(x_i) - P(x_j)| = x_i - x_j$ for all $i<j$.

Claim.

$P(x_i) \neq P(x_j)$ for any $i \neq j$.

Proof.

For the sake of contradiction, suppose the claim statement is wrong. Without loss of generality, suppose $i>j$.

Then, $P(x_i)=P(x_j) => P(x_i)-P(x_j)=0 => |P(x_i)-P(x_j)|=0 => x_i - x_j = 0 => x_i=x_j$, a contradiction.

Hence, our claim is proved.


Claim.

$P(x_1),...,P(x_{n+1})$ is either increasing or decreasing.

Proof.

We will only prove the increasing part, as the decreasing part is similar.

For the sake of contradiction, suppose the claim statement is wrong. Then, $P(x_{i-1})>P(x_i)$ and $P(x_i)<P(x_{i+1})$ for some integer $i>1$.

For convinience's sake, suppose $i=2$.

Then, $|P(x_1)-P(x_2)|=P(x_1)-P(x_2)=x_2-x_1$ and $|P(x_3)-P(x_2)|=P(x_3)-P(x_2)=x_3-x_2$.

Adding, we get that $(P(x_1)+P(x_3))-2 \cdot P(x_2) = x_3 - x_1$.

Now, $x_3 - x_1$ will either be substituted by $P(x_1)-P(x_3)$ or $P(x_3)-P(x_1)$.

Either way, we get a contradiction to our previous claim.

Hence, $P(x_2)>P(x_3)$. Similarly, $P(x_3)>P(x_4)$,...,$P(x_n)>P(x_{n+1})$.

Then, $P(x_1)>...>P(x_{n+1})$.

One may similarly show the decreasing part.

Hence, our claim is proved.


Case 1, The sequence $P(x_1),...,P(x_{n+1})$ is decreasing:

Let $T(x)=(P(x)-x)-(P(x_1)-x_1)$.

Then, $T(x)$ has $n+1$ roots: $x_1,...,x_{n+1}$, while $deg(T)=deg(P)=n$, a contradiction.

One may similarly show the contradiction if the sequence $P(x_1),...,P(x_{n+1})$ is increasing.


Hence, we get our desired contradiction, and thus we are done.

Resources

2006 IMO (Problems) • Resources
Preceded by
Problem 4 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 6
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_IMO_Problems/Problem_5&oldid=261980"