Permutations

[lapras]

Salut,
Voici un problème que je n'ai pas résolu et qui m'a pas l'air évident (j'ai quelques idées).
Je veux montrer que pour toute permutation de , il existe une permutation circulaire de telle que soit partitionnée en ou moins blocs de nombres rangés en ordre croissants puis ou moins blocs de nombres rangés en ordre décroissant.

Exemple :

= 8, 5, 4, 12, 10, 1, 7, 3, 2, 6, 11, 9
= 6,....... 11, 9, 8, 5, 4,.......12, 10, 1,.......7, 3, 2
en bleu les blocs croissants, en rouge les décroissants
il y a moins de 12/4 + 1 = 4 blocs bleu (croissants, il y en 1) et moins de 4 blocs rouges (décroissants, il y en a 3)



Si vous avez des idées, n'hésitez pas !
Lapras :we:

[Doraki]

Ca me paraît peu vraisemblable.

Pour n suffisemment grand, la permutation
1 n 2 (n-1) 3 (n-2) .....
devrait poser problème, non ?

[lapras]

Non ca ne pose pas de problemes :
c'est bien de l'ordre de n/4 ! (je crois que c'est pile [n/4]+1, c'est pour ca que j'ai ajouté +1)
faut bien se dire que n/4 ca revient à partitionner en blocs de tailles moyenne 2 ce qui est le cas.
ca montre d'ailleurs que si l'énoncé est vrai c'est le meilleurs possible pour la majoration du nombre de blocs.

[lapras]

Alors aucune idée ?

[Doraki]

Ah oui y'a pas de problème.
Il me paraît plus simple de raisoner sur le cycle des différences et de s'intéresser aux changements de signes.
Parcequ'on a quelques choix dans notre découpage, oui, mais bien localisés.

[lapras]

Ca revient a regarder les "montées" (signe +) et les "descentes" (signe -)

[lapras]

Un petit up...

[Doraki]

Si on oublie les nombres et qu'on retient seulement la décroissance / croissance, on doit étudier des suites (ou plutôt des cercles) de "+" et de "-".
On peut se restreindre aux cercles qui ne contiennent pas de triplets "+++" ou "---".
Blocs croissants : +, -, ++, -+, -++.
Blocs décroissants : +, -, +-, --, +--.

Je dirais qu'il faut faire en truc comme prendre le plus possible de blocs croissants "-++", puis de "-+" jusqu'à arriver à la limite, puis de couvrir le reste avec des blocs décroissants.

[lapras]

Je ne suis pas sur qu'on puisse affirmer qu'on peut se restreindre aux cercles qui ne contiennnent pas de +++ et ---.
Un --- en plein milieu de nos blocs croissants est bien embetant.

[lapras]

Sans les "+++" ou "---" je pense avoir une démo.

[lapras]

Voici mon idée.
Si il n'y a pas de +++ ou ---,
soit a le nombre de ++ et b le nombre de --.
Si S=a+b=0, notre suite de + et de - est de la forme +-+-+-+-....
dans ce cas il est facile de voir qu'on peut diviser n'importe quelle suite de taille n (pour tout n)de cette forme en [n/4]+1 ou moins blocs croissants puis [n/4]+1 ou moins blocs décroissants, ainsi qu'en [n/4]+1 ou moins blocs décroissants puis [n/4]+1 ou moins blocs croissants.
On résonne par récurrence sur S=a+b
soit : P_k : "Toute suite de longueur n (pour tout n) avec la propriété a+b=k peut se diviser en soit [n/4]+1 ou moins blocs croissants puis [n/4]+1 ou moins blocs décroissants, soit en [n/4]+1 ou moins blocs décroissants puis [n/4]+1 ou moins blocs croissants."
Si P_0 est vraie.
Si P_k est vraie pour un k, on regarde P_{k+1}
soit sigma n'importe quelle suite de + et - de taille n. (n quelconque).
Il existe dans sigma un bloc "++" ou "--" (k+1>=1).
sans perte de généralité c'est "++".
On écrit notre suite sur un cercle (on raisonne dans le sens non trigo), on supprime un des deux "+", on applique l'hypothese de récurrence (a+b=k pour la suite obtenue en supprimant le +) et P_{k+1} vraie (car [(n-1)/4]<=[n/4] et on "intègre" les "++" au premier ou dernier bloc cri)
Par récurrence P_k vraie pour tout k.
Je pense que ca marche...
Et ca se généralise je crois quand on récurre sur m puis sur la somme de "+++...+" m fois et "-----...-" m fois avec m la taille du plus grand bloc de "+" consécutifs ou "-" consécutifs...
Qu'en pensez vous ?

[lapras]

peut etre une idée.
je prend une suite de et de - du cercle, de taille .
je note b le nombre de et a le nombre de -.
On a : .
Je note la séquence de termes consécutifs, dans le sens non trigo, commençant par et de taille .
Enfin je note le nombre de dans .
Je suppose par l'absurde que , ,
Alors :

mais, car on compte chaque fois.
d'où :

comme ,
d'où :

absurde
D'où : tel que

sur notre cercle on prend alors notre sous suite B_i de termes consécutifs et de taille (tout ca dans le sens non trigo),
il y a moins de dedans donc on peut faire moins de blocs décroissants.
Il y a plus de - dans
Pour le restant du cercle (de à dans le sens non trigo), il y a moins de signe -.
donc moins de blocs croissants.
D'où la conclusion.
Ca vous parait cohérent ?