Aller au contenu

Shortlist 2006, N4

Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : Romania

Concepts : Polynômes à coefficients entiers · Divisibilité, PGCD et algorithme d'Euclide

Solution officielle : Shortlist officielle 2006 (avec solutions), p. 58 (page 59 du PDF)

Problème 5 de l'OIM 2006

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2006, où il était le problème 5 (jour 2).

Énoncé

Let \(P\) be a polynomial of degree \(n > 1\) with integer coefficients and let \(k\) be any positive integer. Consider the polynomial \(Q(x) = P(P(\ldots P(P(x)) \ldots))\), with \(k\) pairs of parentheses. Prove that \(Q\) has no more than \(n\) integer fixed points, i.e. integers satisfying the equation \(Q(x) = x\).

Indices : les idées clés
  • Divisibilité : \(u - v \mid P(u) - P(v)\) ; le long d'un cycle, les différences successives se divisent et ont donc même valeur absolue, d'où des orbites de longueur au plus \(2\).
  • Deux 2-orbites : si \(P(a) = b \neq a\), \(P(b) = a\), et \(\alpha\), \(\beta = P(\alpha)\) est un autre point fixe de \(P \circ P\), alors \(\alpha + \beta = a + b\).
  • Comptage des racines : tous les points fixes entiers de \(Q\) sont racines du polynôme \(a + b - x - P(x)\), de degré \(n\).
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2006 (une solution et une remarque). C'est le problème 5 de l'OIM 2006.

Solution

L'affirmation est évidente si chaque point fixe entier de \(Q\) est un point fixe de \(P\) lui-même. Supposons dans la suite que ce n'est pas le cas. Prenons un entier \(x_0\) quelconque tel que \(Q(x_0) = x_0\), \(P(x_0) \neq x_0\), et définissons par récurrence \(x_{i+1} = P(x_i)\) pour \(i = 0, 1, 2, \ldots\) ; alors \(x_k = x_0\).

Il est clair que

\[P(u) - P(v) \text{ est divisible par } u - v \text{ pour des entiers distincts } u, v. \tag{1}\]

(En effet, si \(P(x) = \sum a_ix^i\), alors chaque \(a_i(u^i - v^i)\) est divisible par \(u - v\).) Donc chaque terme de la chaîne de différences (non nulles)

\[x_0 - x_1, \quad x_1 - x_2, \quad \ldots, \quad x_{k-1} - x_k, \quad x_k - x_{k+1} \tag{2}\]

divise le suivant ; et comme \(x_k - x_{k+1} = x_0 - x_1\), toutes ces différences ont la même valeur absolue. Pour \(x_m = \min(x_1, \ldots, x_k)\), cela signifie que \(x_{m-1} - x_m = -(x_m - x_{m+1})\). Donc \(x_{m-1} = x_{m+1}\) \((\neq x_m)\). Il s'ensuit que des différences consécutives de la suite (2) sont de signes opposés. Par conséquent, \(x_0, x_1, x_2, \ldots\) est une suite alternant entre deux valeurs distinctes. Autrement dit, tout point fixe entier de \(Q\) est un point fixe du polynôme \(P(P(x))\). Notre tâche est de prouver qu'il y a au plus \(n\) tels points.

Soit \(a\) l'un d'eux, tel que \(b = P(a) \neq a\) (on a supposé qu'un tel \(a\) existe) ; alors \(a = P(b)\). Prenons tout autre point fixe entier \(\alpha\) de \(P(P(x))\) et posons \(P(\alpha) = \beta\), de sorte que \(P(\beta) = \alpha\) ; les nombres \(\alpha\) et \(\beta\) ne sont pas forcément distincts (\(\alpha\) peut être un point fixe de \(P\)), mais chacun de \(\alpha\), \(\beta\) est différent de chacun de \(a\), \(b\). En appliquant la propriété (1) aux quatre couples d'entiers \((\alpha, a)\), \((\beta, b)\), \((\alpha, b)\), \((\beta, a)\), on obtient que les nombres \(\alpha - a\) et \(\beta - b\) se divisent mutuellement, de même que \(\alpha - b\) et \(\beta - a\). Par conséquent

\[\alpha - b = \pm(\beta - a), \qquad \alpha - a = \pm(\beta - b). \tag{3}\]

Supposons qu'on ait un signe plus dans les deux cas : \(\alpha - b = \beta - a\) et \(\alpha - a = \beta - b\). La soustraction donne \(a - b = b - a\), ce qui est une contradiction, puisque \(a \neq b\). L'une au moins des égalités de (3) a donc un signe moins. Pour chacune d'elles, cela signifie que \(\alpha + \beta = a + b\) ; de façon équivalente, \(a + b - \alpha - P(\alpha) = 0\).

Notons \(C = a + b\). On a montré que tout point fixe entier de \(Q\) autre que \(a\) et \(b\) est racine du polynôme \(F(x) = C - x - P(x)\). C'est bien sûr vrai aussi pour \(a\) et \(b\). Et comme \(P\) est de degré \(n > 1\), le polynôme \(F\) a le même degré, donc il ne peut pas avoir plus de \(n\) racines. D'où le résultat. \(\blacksquare\)

Remarque

La première partie de la solution, qui montre que les points fixes entiers de toute itérée de \(P\) sont en fait des points fixes de la deuxième itérée \(P \circ P\), est classique ; ce fait est d'ailleurs déjà apparu dans des compétitions. On ne considère cependant pas cela comme un défaut majeur du problème, car la seule difficulté apparaît à l'étape suivante du raisonnement : appliquer la propriété de divisibilité (1) à des points de 2-orbites distinctes de \(P\). Il serait peut-être plus approprié d'énoncer le problème dans une version avec \(k = 2\) seulement.