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"

(→‎Solution: typo fixed, thanks hello123)
(→‎Solution: grammar fixed)
Line 10: Line 10:
 
'''Lemma 1.''' The problem statement holds for <math>k=2</math>.
 
'''Lemma 1.''' The problem statement holds for <math>k=2</math>.
  
−
''Proof.''  Suppose that <math>a_1, \dotsc, a_k</math>, <math>b_1, \dotsc, b_k</math> are integers such that <math>P(a_j) = b_j</math> and <math>P(b_j) = a_j</math> for all indices <math>j</math>.  Let the the set <math>\{ a_1, \dotsc, a_k, b_1, \dotsc, b_k \}</math> has <math>m</math> distinct elements.  It suffices to show that <math>\deg (P) \ge m</math>.
+
''Proof.''  Suppose that <math>a_1, \dotsc, a_k</math>, <math>b_1, \dotsc, b_k</math> are integers such that <math>P(a_j) = b_j</math> and <math>P(b_j) = a_j</math> for all indices <math>j</math>.  Let the set <math>\{ a_1, \dotsc, a_k, b_1, \dotsc, b_k \}</math> have <math>m</math> distinct elements.  It suffices to show that <math>\deg (P) \ge m</math>.
  
 
If <math>a_j = b_j</math> for all indices <math>j</math>, then the polynomial <math>P(x)-x</math> has at least <math>m</math> roots; since <math>P</math> is not linear, it follows that <math>\deg P \ge m</math> by the division algorithm.
 
If <math>a_j = b_j</math> for all indices <math>j</math>, then the polynomial <math>P(x)-x</math> has at least <math>m</math> roots; since <math>P</math> is not linear, it follows that <math>\deg P \ge m</math> by the division algorithm.

Revision as of 06:40, 8 February 2009

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+1}),\] 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.

Resources

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>
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_IMO_Problems/Problem_5&oldid=30011"