Bonjour, je viens me joindre à votre bagare. La réponse d'Imod est bien penser. Cependant sauf si j'ai loupé quelque chose ce qui est tres probable du fait que j'ai tout lu vite fait, il manque quelque chose : En appelant X une configuration de tas, T(x) la configuration apres une iteration,
tu demontre que l'eloignement total (noté I) I(Tx)=x_2>=...>=x_{45}\}$[/TEX]
Nous appellons T: V_2->V_2 la transformation de l'enoncé.
Nous allons decomposer T en deux transformation (T(x)=T2(T1(x))
T2: V -> V2 qui est l'opération de trie par ordre décroissant
et
T1 : V2 -> V
(avec
si x>0, 0 sinon)
Nous aurons donc
et d'apres le lemme
dans ce cas à la prochaine iteration T2 effectuera une modification diminuant
- sinon s'il y a un triplet (ou plus long) ( x_i=x_i+1=x_i+2) Apres quelques iterations on aura a la fin de la chaine X : 1, 1, 1
On a alors
(du fait qu'a l'iteration suivante les 3 1 vont disparaitres) Nous aurons alors à literation d'apres
et T2 effectuera alors une permutation qui diminuera
- Enfin s'il n'y a pas de triplet c'est qu'il y a 2 doublets et la c'est la merde
Prenons par exemple 9 9 7 6 5 4 2 2 1, Il faut 10 iterations pour diminuer
. Bon je n'ai pas envi de reflechir à pourquoi ca finit par diminuer mais si quelqu'un a envi ne vous gener pas.
Voila bon courage pour comprendre ce que j'ai marqué