Suite extraite...

[Ben314]

En rangeant mon b....., je suis tombé sur un livre qui représente (pour moi) une "bible" de casse-tête (l'auteur est P.H.).

Pour ceux qui connaissent pas, en voila un (déjà vu ?) :

On se donne un entier k.
Existe t'il un entier n tel que, de toute suite de n nombres réels on puisse extraire (dans l'ordre !!!) une sous suite monotone de longueur k ?
Si oui, quel est (en fonction de k) le plus petit n possible ?


Un autre problème qui lui ressemble (mais pas tiré du bouquin) :
Je me suis posé une fois la question de savoir si on pouvait montrer que toute suite réelle bornée admet une sous suite convergente (niveau L1 ou L2) en utilisant le fais que les suites bornées monotone sont convergente (admis en Term).
La question : Peut on extraire d'une suite quelconque une suite monotone ?
(En fait je sais pas si on en a pas déja parlé sur le forum. Si oui, désolé, je radotte : c'est la vieillerie...)

[Nightmare]

Salut !

Le deuxième est assez intuitif en considérant les ensembles de rang ou la suite présente un extremum. Autrement dit, on considère les ensembles de n tels que pour tous les rangs supérieur à n, les termes sont inférieurs ou supérieur à u(n). On dégage des sous-suites monotone selon la finitude de ces ensembles. Bref, je ne détaille pas mais la construction se voit.

Je réfléchis au second, moins classique :lol3:

[Ben314]

Le deuxième est assez intuitif...
Je réfléchis au second...

Quand tu auras fini le second, tu pourra attaquer celui qui est juste aprés le premier, il est bien. Ensuite quand tu auras fini, cherche aussi celui juste avant le troisième, il est pas mal non plus, aprés.... :zen:
Comme quoi, je suis pas le seul à radoter... :marteau:

[Nightmare]

Si tu me cherches... :lol3:

En cherchant le premier, je me suis rendu compte que je l'avais déjà résolu en TD d'informatique, avec une histoire de chaines et de graphes... Je ne me rappelle plus de la preuve exacte cela dit, mais juste de l'idée : principe des tiroirs. Je vais essayer de remettre ça au propre.

Deux jolis exercices en tout cas:happy3:

Au passage, je me suis posé la question de savoir ce qu'avait R en plus par rapport aux autres pour que ces théorèmes soient vrais dans cet ensemble et je pense, en attendant ta con/infirmation, que c'est simplement la propriété de la borne sup. Qu'en penses-tu?

[Ben314]

Tu parle des résultats sur les suites dans R (suites extraites et suites croissante et majorée) ?
Je comprend pas bien la question...
Le résultat sur les suites extraites se généralise à tout compact métrique celui sur les suites croissantes me semble se généraliser à tout compact ordonné...

P.S. Si la question c'est par rapport aux quotients (ou aux algébriques de R ou aux décimaux...) qui n'ont pas les propriété en question, a mon sens, on fabrique R exprés pour qu'il ait cette propriété, et celon la façon dont tu le fabrique, les résultats vont se déduire... de ce que tu as fait pour le fabriquer (complété au sens cauchy ou coupures de dedekind ou...)

[Nightmare]

Je pose ma question autrement si tu veux :

Comment caractériser un ensemble ordonné K qui soit tel que toute suite de K admette une sous-suite monotone ?

Suffit-il que ce soit un corps qui possède la propriété de la borne sup?

[Ben314]

Comment caractériser un ensemble ordonné K qui soit tel que toute suite de K admette une sous-suite monotone ?

Réponse simple : il suffit qu'il soit bien ordonné (regarde ta preuve, il n'y a pas besoin de "borne sup", mais seulement de la notion de "max")

[nodgim]

Après qq essais, il semble que jusqu'à k² nombres, on peut limiter la suite à k nombres...
2 avec 4 nombres
3 avec 9 nombres
...?

[Doraki]

Réponse simple : il suffit qu'il soit bien ordonné (regarde ta preuve, il n'y a pas besoin de "borne sup", mais seulement de la notion de "max")

Tu veux dire quoi par "bien ordonné" ?
Il me semble que le résultat est valable dès qu'on a un ordre total.

[Ben314]

Tu veux dire quoi par "bien ordonné" ?
Il me semble que le résultat est valable dès qu'on a un ordre total.

Tout à fait, c'est un lapsus de ma part, désolé....

P.S. Je pourait aussi tenter d'expliquer que, comme en fait le raisonement ce fait sur des parties finie... tout ça... tout ça... mais j'ai un peu du mal...

[Ben314]

Après qq essais, il semble que jusqu'à k² nombres, on peut limiter la suite à k nombres...
2 avec 4 nombres
3 avec 9 nombres
...?

Me semble être une bonne intuition.........

[nodgim]

Soit dans un repère orthonormé, on dessine les points d'abscisse entière 0 à k-1 et d'ordonnée entière 0 à k-1. Il y a donc k² points.
On fait pivoter de qq degrés le repère orthonormé, de sorte qu'il n'y a pas 2 pts à même abscisse ni à même ordonnée.
Maintenant, si on dit que l'axe des x est le classement de la suite des nombres, et l'axe des y la valeur de ces nombres, et que les points tracés sont ces nombres, il est évident que le nombre maxi de nombres d'une suite monotone est k.

[Ben314]

Excellent.
On peut d'ailleurs en déduire un exemple "pur numérique", à savoir la suite :
k, k-1 , k-2, ..., 3 , 2 , 1 / 2k , (2k-1) , ... , k+1 , k / 3k, 3k-1, ... , 2k+1 , 2k / . . . . . / k² , k²-1 , ... , k²-k+2 , k²-k+1

Reste à montrer que, si n>k², on peut FORCEMENT trouver une sous suite monotone de longueur k.....

[ffpower]

Même contrexemple que Ben pour moi..

Reste à montrer que, si n>k², on peut FORCEMENT trouver une sous suite monotone de longueur k.....

De longueur k+1, tu veux dire..

[nodgim]

Reste à montrer que, si n>k², on peut FORCEMENT trouver une sous suite monotone de longueur k.....

Oui, et ce n'est pas le plus simple, car il n'est pour l'instant pas prouvé que la configuration présentée est la meilleure....

[poiuytreza]

En fait c'est un résultat connu (enfin, plus ou moins... :we: ) sous le nom de "Théorème d'Erdös-Szekeres".
La démonstration que je connais est assez jolie :

Supposons qu'on a une suite de longueur ne contenant aucune sous-suite monotone de longueur
On associe alors à chaque i la paire où est la longueur de la plus grande sous-suite croissante commençant par et la longueur de la plus grande sous-suite décroissante commençant par
D'après l'hypothèse, et sont compris entre et , donc par le principe des tiroirs, il existe i et j distincts tels que et . En regardant les différents cas et , on voit facilement que c'est impossible.

[nodgim]

. En regardant les différents cas et , on voit facilement que c'est impossible.

Facilement, je veux bien, pourtant, je trouve des paires identiques avec 10 nombres placés au hasard, par exemple avec la suite:
5,2,9,7,4,1,6,8,10,3.

[poiuytreza]

Je crois que ça marche quand même (de toute façon, la preuve vient d'un bouquin donc en principe il n'y a pas d'erreur :we: )

On suppose , puisqu'on peut considérer la plus grande sous-suite croissante commençant par , et y ajouter au début, ce qui fait une sous-suite croissante de longueur donc .
Le raisonnement est le même dans l'autre cas : si , alors .

Pour ton exemple, les couples sont (si je ne fais pas d'erreur):
(4,3)
(5,2)
(2,4)
(3,3)
(4,2)
(4,1)
(3,2)
(2,2)
(1,2)
(1,1)
donc les couples sont bien tous distincts.

[Ben314]

Bien joué à tous....
La preuve que je connaissait est celle des "tiroirs" de poiuytreza. (sauf que perso, je considère les suites croissantes de DERNIER terme ai, ce qui ne change absolument rien)
Le site suivant :
http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem
propose une "seconde" preuve qui pourrait être celle vu par doraki en TD d'info.

[Nightmare]

Je pense tenir quelque chose :

Je considère ma suite d'au moins k² termes x1, x2,....,xk². En partant de x1, je retire des termes au fur et à mesure de manière à obtenir la plus grande sous-suite monotone, disons décroissante. Je réitère le procédé avec les termes restant etc. jusqu'à ne plus avoir de terme.

Si je suppose que ma plus grande suite décroissante a au plus k termes au sens strict, alors j'ai pu itérer mon procéder d'extraction au moins (au sens strict) k fois. Or, à chaque étape, si je considère un terme restant, on a forcément retiré à l'étape précédente un terme qui le précédait et qui lui était inférieur. Il est alors facile de construire une sous-suie croissante à au moins k termes : Je prends un élément restant à la dernière étape, d'après ce que j'ai dit avant, on peut trouver un élément restant à l'avant dernière étape, le précédant et lui étant inférieur. Je réitère le procéder avec ce dernier élèment etc. A la fin, le dernier élément considérer est le premier de ma suite, l'avant dernier le deuxième etc... j'ai bien une suite croissante d'au moins k élément.

Conclusion : Si je ne peux pas construire de sous-suite décroissante d'au moins k termes, je peux en construire une croissante.

:happy3: