Exercices de MPSI

Obi Wan Kenobi a écrit:

[quote=« charlestiran »]
Pas pendant la prépa en tout cas, et c’est très bien comme ça. J’ai encore le temps - même si faudra bien qu’un jour je m’y mette - même si les maths doivent être la science la moins touchée par cette gangrène :wink:
Gangrène ? Lol. Les étrangers publient en anglais et les français … publient en anglais aussi.
[/quote]
Et puis si tu tiens à collaborer avec des personnes non francophones, il va bien falloir que vous trouviez un langage commun. En pratique, il s’agit plus souvent de l’anglais que de l’ukrainien… Faut faire avec.

Nico_ a écrit:

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(...P(P(x))...)), where P occurs k times. Prove that there are at most n integers t such that Q(t)=t.

Si t est un point fixe de P, alors il est évidemment un point fixe de Q.
Si l’on considère la fonction polynomiale P-\mathbf{Id_R} : x\mapsto P(x)-x, on a \deg(P-\mathbf{Id_R})\leq n. Donc P-\mathbf{Id_R} admet au plus n racines réelles (on le montre facilement par récurrence en utilisant le théorème des valeurs intermédiaires). P a alors au plus n points fixes.
Maintenant, il faut que je montre que les points fixes de Q sont des points fixes de P (ou peut-être de P itéré un certain nombre de fois). C’est ici que je bloque. Je suppose que je devrais utiliser le fait que les coefficients de P sont entiers, mais je ne sais pas trop comment m’en servir. Pourrais-je avoir une indication s’il te plait ?

kköhlc a écrit:

[quote=« Nico_ »]
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(...P(P(x))...)), where P occurs k times. Prove that there are at most n integers t such that Q(t)=t.

Si t est un point fixe de P, alors il est évidemment un point fixe de Q.
Si l’on considère la fonction polynomiale P-\mathbf{Id_R} : x\mapsto P(x)-x, on a \deg(P-\mathbf{Id_R})\leq n. Donc P-\mathbf{Id_R} admet au plus n racines réelles (on le montre facilement par récurrence en utilisant le théorème des valeurs intermédiaires). P a alors au plus n points fixes.
Maintenant, il faut que je montre que les points fixes de Q sont des points fixes de P (ou peut-être de P itéré un certain nombre de fois). C’est ici que je bloque. Je suppose que je devrais utiliser le fait que les coefficients de P sont entiers, mais je ne sais pas trop comment m’en servir. Pourrais-je avoir une indication s’il te plait ?

[/quote]

C’est un peu difficile de donner une indication sans donner la réponse. Disons qu’il y a quelque chose à remarquer sur ces points fixes. Quelque chose de cyclique qui fait que le problème se résout « facilement » si on remarque ça :slight_smile:

Je pense avoir trouvé un truc :

Soit t\in\mathbf{Z} tel que Q(t)=t et P(t)\neq t. On définit par récurrence une suite (t_p)_{p\in\mathbf{N}} telle que t_0=t et t_{p+1}=P(t_p). On a alors t_k=t. Donc \displaystyle t_{k}-t_0=\sum_{p=0}^k (t_{p+1}-t_p)=0. Tous les termes de (t_p)_{p\in\mathbf{N}} sont entiers.
On remarque que t_{p+1}-t_p=P(t_p)-P(t_{p-1}). Or \displaystyle P(t_p)-P(t_{p-1})=\sum_{i=1}^na_i(t_p-t_{p-1})^i. Donc t_p-t_{p-1}|P(t_p)-P(t_{p-1}), d’où t_{p}-t_{p-1}|t_{p+1}-t_p.
Or, on a t_{k+1}=P(t_k)=P(t)=t_1. Donc t_{k+1}-t_k=t_1-t_0. Comme on a t_1-t_0|t_2-t_1|...|t_{k+1}-t_k, on en déduit que tous les t_{p+1}-t_p sont égaux en valeur absolue. Donc déjà, si k est impair, on ne peut pas avoir Q(t)=t parce que la somme des t_{p+1}-t_p ne peut s’annuler. Par contre dans le cas où k est pair…

Edit :

En fait, si la suite (t_p)_{p\in\mathbf{N}} est croissante jusqu’à un certain rang, alors elle est ensuite décroissante (pour obtenir t à la fin). Mais si on prend le point où la suite atteint son maximum, noté t_{max}, alors on a t_{max+1}-t_{max}=-|t_1-t_0| et t_{max}-t_{max-1}=|t_1-t_0| d’où t_{max-1}=t_{max+1}. Donc t_{max+2}=t_{max}. Donc la suite ne peut prendre que deux valeurs différentes. Comme t_k\neq t_{k+1}, on a donc t_{k+2}=t_k donc il faut s’intéresser aux points fixes de P(P(x)).

C’est un excellent début, bravo :smiley:
Je te laisse encore un peu chercher :

Remarquer que les t_{p+1}-t_p sont égaux en valeur absolue peut t’apporter quelque chose. Si tu ne vois pas regarde le spoiler suivant.

Considère t_m=min(t_1,...,t_k). Alors t_{m-1}=t_{m+1} et donc…

Edit pour ton edit : bien joué :slight_smile: C’était là le cœur du problème.

corderaide a écrit:

[quote=« V@J »]

[quote=« Obi Wan Kenobi »]
Gangrène ? Lol. Les étrangers publient en anglais et les français … publient en anglais aussi.
Et puis si tu tiens à collaborer avec des personnes non francophones, il va bien falloir que vous trouviez un langage commun. En pratique, il s’agit plus souvent de l’anglais que de l’ukrainien… Faut faire avec.
[/quote]
Et comment tu peux aller draguer les ukrainiennes après si tu sais parler que Français ? 'Tain les jeunes n’ont plus le sens pratique de nos jours…
[/quote]
Quand on est X, pas besoin de savoir ukrainien ou même anglais, on a l’argent qui est la langue universelle :sunglasses:

brank a écrit:

Pour rester dans les proba/combinatoire,un plus facile, histoire que des TS (autres que kkölc) puissent chercher.

Montrer pour n,l entiers positifs l’égalité:
\binom{n+l}{n}= \sum\limits_{k = 0}^l \binom{n+k-1}{n-1}
En restant dans le calculatoire :

On cherche à montrer que P(n) :$\sum_{k=0}^{l}\binom{n+k-1}{n-1}=\binom{n+p}{n}est vraie. On montre P(1) vraie. P(1) : \sum_{k=0}^{l}\binom{1+k-1}{1-1}=\sum_{k=0}^{l}\binom{k}{0} = 1+l et \binom{1+l}{1} = \frac{(1+l!)}{1!l!}=1+l$.
On suppose P(n) vraie et on montre P(n+1) vraie.
\sum_{k=0}^{l}\binom{n+k}{n}= \sum_{k=0}^{l}\frac{n+k}{n}\binom{n+k-1}{n-1}= \sum_{k=0}^{l}\binom{n+k-1}{n-1}+\sum_{k=0}^{l}\frac{k}{n}\binom{n+k-1}{n-1}
D’après l’hypothèse de récurrence, on a :
P(n+1) : \binom{n+p}{n}+\sum_{k=1}^{l}\binom{n+k-1}{n}=\binom{n+p}{n}+\binom{n+p}{n+1}=\binom{n+p+1}{n+1}
Donc P(n+1) est vraie. On en déduit que P(n) est aussi vraie.

:3

Here we go !
Je récapitule (en anglais comme l’énoncé était en anglais :grin: )

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(...P(P(x))...)), where P occurs k times. Prove that there are at most n integers t such that Q(t)=t.

[spoiler]Let P:\mathbf{R}\to\mathbf{R} denote the function \displaystyle x\longmapsto\sum_{i=0}^na_ix^i where the (a_i)_{0\leq i\leq n} are integers,with a_n\neq 0.

**Lemma I. ** For all integers x,y such that x\neq y, x-y|P(x)-P(y).
Proof. \displaystyle P(x)-P(y)=\sum_{i=0}^na_ix^i-\sum_{i=0}^na_iy^i=\sum_{i=1}^na_i(x^i-y^i). Hence the result.\square

Let t\in\mathbf{N} be such that Q(t)=t and P(t)\neq t.
Let’s define a sequence (t_i)_{i\in\mathbf{N}} such that t_0=t and t_{i+1}=P(t_i). All of its terms are integers, of course.
From Lemma I, it follows that t_{i}-t_{i-1} divides P(t_{i})-P(t_{i-1}), which is equal to t_{i+1}-t_i. Moreover, t_1-t_0=t_{k+1}-t_k, since t_k=t_0=t.
Since we have t_1-t_0|t_2-t_1|...|t_{k+1}-t_k, we can remark that |t_{i+1}-t_{i}| remains constant.
The set (a_i)_{0\leq i\leq k} is finite, hence it has a maximal element, denoted t_{max}. It follows that t_{max}-t_{max-1}=+|t_{i+1}-t_i| and that t_{max+1}-t_{max}=-|t_{i+1}-t_i|.
So we have t_{max-1}=t_{max+1}. Using mathematical induction, we get that the sequence (t_i)_{i\in\mathbf{N}} is composed of only two different values.
Therefore, if t is a fixed point of Q, it is either a fixed point of P or P^2 (denoting P\circ P).
It is evident that if t is a fixed point of P, then it is a fixed point of P^2.
Now let a, b\in\mathbf N be two fixed points of P^2, such that P(a)\neq P(b) and a\neq P(a). From lemma I, a-b|P(a)-P(b) and P(a)-P(b)|a-b, hence a-b=\pm(P(a)-P(b))
We also notice that P(a)-b|a-P(b) and a-P(b)|P(a)-b, hence P(a)-b=\pm(a-P(b)).
Two plus in the previous equations lead to the contradictory equality a=P(a). At least one equation has a minus sign, which leads to the following : a+P(a)=b+P(b).
If a is fixed, then t\in\mathbf{N} is a fixed point of P^2 if it is a root of the equation 0=a+P(a)-x-P(x). However, the polynomial a+P(a)-x-P(x) has degree n.

Lemma II. An $n$th degree polynomial has at most n real roots.
Proof. Evident from the intermediate value theorem, using mathematical induction on n.\square

Hence there are at most n fixed points for P^2, which leads to the following : they are at most n integers t such that Q(t)=t.[/spoiler]

Well done !

Bon l’année prochaine, ne va pas t’exiler à Paris et va au Parc (non je ne sais pas où tu habites, oui je dis ça au hasard :stuck_out_tongue:).

Edit : quand même, je trouve ce résultat surprenant (je parle du problème que tu viens de résoudre).

non non saint-louis c’est vraiment cool :stuck_out_tongue:

Nico_ a écrit:

Well done !

Bon l’année prochaine, ne va pas t’exiler à Paris et va au Parc (non je ne sais pas où tu habites, oui je dis ça au hasard :stuck_out_tongue:).
Merci!
Pour l’autre problème il faudra attendre ((très) longtemps), car il est à l’air encore plus costaud (surtout que pour celui là j’ai eu de la chance, j’avais lu le cours sur les polynômes il y a peu de temps, donc les deux lemmes bien utiles me sont vites revenus :slight_smile: ). Je suis assez exécrable en géométrie btw :frowning: (pourvu qu’il n’y en ait pas au CG… :blush: ), d’ailleurs si quelqu’un connait un bouquin de géométrie sympa (et pas trop dur), je suis preneur.

Pour ton edit : Je me suis dit ça aussi au début, normalement Q est de degré au plus n^k, donc il aurait au plus n^k racines, alors que en fait il n’en a qu’au plus n. :unamused:

Pour les lycées, je réfléchis déjà pas mal donc n’essayez pas de me tirailler encore plus :grin: !

kköhlc a écrit:

Pour l’autre problème il faudra attendre ((très) longtemps), car il est à l’air encore plus costaud (surtout que pour celui là j’ai eu de la chance, j’avais lu le cours sur les polynômes il y a peu de temps, donc les deux lemmes bien utiles me sont vites revenus :slight_smile: ). Je suis assez exécrable en géométrie btw :frowning: (pourvu qu’il n’y ait pas au CG… :blush: ), d’ailleurs si quelqu’un connait un bouquin de géométrie sympa (et pas trop dur), je suis preneur.
Comme d’hab je vais recommander mes classiques : moi j’ai tout appris sur La géométrie du triangle.
kköhlc a écrit:
Pour ton edit : Je me suis dit ça aussi au début, normalement Q est de degré au plus n^k, donc il aurait au plus n^k racines, alors que en fait il n’en a que n. :unamused:
Bah ouais :slight_smile:

Pour la géométrie élémentaire, pour une préparation sérieuse au CG, je pense que ceci peut faire l’affaire : La géométrie du triangle
amazon.fr/La-g%C3%A9om%C3%A9 … 270561429X

En fait, si on avait le droit d’obliger à quelqu’un d’acheter quelque chose, je t’aurais obligé de l’acheter, si ce n’est pas déjà fait :wink:

Edit : bah Nico vient juste d’en parler…

Merci du conseil :slight_smile: . (et merci de la part d’amazon.fr aussi :grin: )
Je vais faire un peu d’arithmétique pour patienter !

Il paraît que cela forge le raisonnement. Apparemment c’était le livre de chevet de M. Cédric Villani pendant ses années collège. Cela fait déjà deux personnes de Ulm qui le recommandent :slight_smile:

Ce livre est si intéressant que ça ? Comment est-il organisé ? :astonished:

Je vais finir par me le prendre aussi, à vous écouter. :slight_smile:

D’autresss exercices :smiley: ?

Pour le livre : bah… rien d’exceptionnel dans son organisation. Je posterai un exo issu de ce livre dans les jours qui suivent si j’ai le droit.

Animak : quel thème ? Quelle difficulté ?

Comme tu veux Nico !
EDIT : Un sympathique pour commencer :stuck_out_tongue:

Bonjour,

Un petit exercice classique : développer (x-a)(x-b)\ldots(x-z).