séquences monotones mais distrayantes

[invite35452583]

Bonjour à tous,
un petit problème de "chaussettes"
une séquence est la donnée dans un certain ordre de n nombres (ici distincts) :

Elle est dite croissante si :

Elle est dite décroissante si :

Elle est dite monotone si elle est croissante ou décroissante.

En général une suite n'est pas monotone mais peut contenir des sous-séquences qui le sont :
215463 n'est pas monotone mais par exemple les sous-séquences 256, 246, 156 le sont ainsi que 543.

On s'intéresse à la longueur de ces sous-séquences monotones.
Toute séquence de longueur au moins 2 contient au moins une sous-séquence de longueur 2, or une séquence de longueur 2 est monotone.
Pour 3 ?
213 est un exemple d'une séquence de longueur 3 non monotone
3142 est un exemple de séquence de longueur 4 ne contenant aucune sous-séquence monotone de longueur 3.
Par contre une séquence de longueur 5 contient toujours une séquence monotone de longueur 3. (Je vous laisse vous en convaincre)

Est-ce que pour tout entier k, il existe un entier n tel que pour toute séquence de longueur au moins n on peut trouver une sous-séquence monotone de longueur au moins k ?
Si oui, quel est le plus petit de ces n (en fonction de k) ?
Si non quel est le plus petit des k pour lequel n n'existe pas ?
-----

[invite35452583]

Allez 2 indications :
la réponse est oui, il existe, pour toute longueur k des sous-séquences monotones, une longueur n telle toute séquence de longueur au moins n contient au moins une sous-séquence de longueur k (voir plus évidemment).
k...n
2...2
3...5
4...10
5...17
...
Reste à trouver la formule liant k et n et montrer le résultat (c'est plus facile avec la formule ), à savoir , d'une part,montrer que longueur n de la séquence=>sous-séquence monotone de longueur k et, d'autre part, trouver pour chaque k une séquence de longueur n-1 ne contenant pas de sous-séquence monotone de longueur k-1.

"problème de "chaussettes"" car le plus direct est d'appliquer le principe des tiroirs mais reste à trouver les objets (les "chaussettes" ) auxquels l'appliquer.

[yat]

J'ai essayé de partir dans une direction un peu algorithmique : Je cherche à construire le plus petit nombre de sous-séquences croissantes. En gros, je construis en parallèle un certain nombre de sous-séquences distinctes, à chaque fois que je tombe sur un élément qui est inférieur à tous les derniers termes des sous-séquences en cours, j'en crée une nouvelle. Sinon, je l'ajoute à la première séquence qui me tombe sous la main.

Bon, je ne sais pas si pour avoir le plus petit nombre de sous-séquences croissantes, cet algotithme est optimal, mais l'intérêt c'est que je peux construire avec ce découpage une sous séquence décroissante comprenant autant d'éléments que j'ai de sous-séquences croissantes. Comme ça je vais me retrouver avec une borne inférieure de l'ordre de la racine carrée, et les premières valeurs que tu donnes semblent suivre ce genre de loi. J'ai un peu de mal à le démontrer formellement avec des mots, mais en partant de la fin de la dernière sous-séquence croissante, je peux piocher dans chaque sous-séquence l'élément qui a précédé à la création de la sous-séquence suivante.

Du coup, si dans ma séquence de longueur n, j'ai x sous-séquences décroissantes, je dispose d'une sous-séquence décroissante de taille x, et au moins d'une sous-séquence croissante de taille n/x arrondi à l'entier supérieur. Je peux donc choisir la plus grande, qui sera nécessairement au moins égale à la racine de n, arrondie à l'entier supérieur, puisque x>=n/x équivaut à x²>=n pour x et n strictement positifs.

Etant donné la taille k de la sous-séquence voulue, je cherche donc la taille n de la plus petite séquence en contenant nécessairement une. La racine de n-1, arrondie à l'entier supérieur, est donc k-1. Comme c'est la plus grande valeur de n qui respecte cette condition, on a donc même (k-1)²=n-1, soit n=(k-1)²+1.

Ce qui me donne les mêmes résultats numériques que toi !

[invite35452583]

Salut yat,
tes explications me sont encore un peu nébuleuses

Si je comprends bien sur un exemple
135246
1 : début de la 1ère sous-séquence croissante
3 (>1)=>13
5 (>3)=>135
2 (<5)=>début d'une seconde sous-séquence croissante
4 (>2)

à chaque fois que je tombe sur un élément qui est inférieur à tous les derniers termes des sous-séquences en cours, j'en crée une nouvelle. Sinon, je l'ajoute à la première séquence qui me tombe sous la main.

Ici ce n'est pas clair car on est bien dans la situation du "sinon" mais je ne peux ajouter "4" à la 1ère sous-séquence sans lui retirer son caractère croissant.
4 (>2 mais <5)=>24
On en est à 135 et 24
terme suivant 6 >4 et >5
je l'ajoute à la 1ère séquence qui me tombe sous la main, pas de bol c'est 24 ainsi on a 135 et 246, mais où est alors la sous-séquence décroissante de longueur x dans ce qui suit (partie que j'ai soulignée) :

Du coup, si dans ma séquence de longueur n, j'ai x sous-séquences décroissantes, je dispose d'une sous-séquence décroissante de taille x, et au moins d'une sous-séquence croissante de taille n/x arrondi à l'entier supérieur.

Ce que j'ai mis en gras c'est bien "croissantes" qu'il faut lire, non ?

Déjà bravo l'idée, je pense (à 99,9%), doit aboutir à une preuve claire et assez simple après quelques "réglages" et éventuellemnt simplifications. De plus la formule est la bonne.

[A voir en vidéo sur Futura]

[yat]

Salut yat,
tes explications me sont encore un peu nébuleuses

Bah on ne se refait pas...
Mais si je laisse des zones floues, ça permet de mettre un peu d'interactivité dans le truc... allons y.

Si je comprends bien sur un exemple
135246
1 : début de la 1ère sous-séquence croissante
3 (>1)=>13
5 (>3)=>135
2 (<5)=>début d'une seconde sous-séquence croissante
4 (>2)

Ici ce n'est pas clair car on est bien dans la situation du "sinon" mais je ne peux ajouter "4" à la 1ère sous-séquence sans lui retirer son caractère croissant.
4 (>2 mais <5)=>24
On en est à 135 et 24
terme suivant 6 >4 et >5
je l'ajoute à la 1ère séquence qui me tombe sous la main, pas de bol c'est 24

En fait, il faut prendre le "première" un peu plus littéralement : la première séquence de ma liste est 135. Du coup j'obtiens 1356 et 24. Pour trouver la séquence décroissante, je pars du 4, et ensuite j'ajoute l'élément qui précède celui qui m'a amené à créer la séquence 24, c'est à dire le 5, puisqu'ensuite il y a eu le 2.

Ce que j'ai mis en gras c'est bien "croissantes" qu'il faut lire, non ?

En effet. Désolé pour le lapsus.

Déjà bravo l'idée, je pense (à 99,9%), doit aboutir à une preuve claire et assez simple après quelques "réglages" et éventuellemnt simplifications. De plus la formule est la bonne.

Merci !

Je pense que la partie qui reste la plus floue est de prouver qu'avec cette construction je vais forcément avoir une séquence décroissante en remontant les listes. Mais pour simplifier, je peux prendre une méthode un peu différente : au lieu de prendre l'élément de la liste précédente qui a précédé la création de la liste courante, je peux me contenter de prendre le dernier élément de la liste précédente au moment ou l'élément que je suis en train de considérer a été lu. Ca me parait plus facile à démontrer : au moment ou j'ai ajouté l'élément courant dans la liste courante, je peux être sur que le dernier élément de la liste précédente était supérieur. Sinon l'élément courant n'aurait pas été ajouté à la liste courante, mais à la liste précédente. Du coup on génère forcément une liste décroissante.

A partir de là, on peut donc montrer que l'autre construction marche aussi : l'élément qui précède celui qui m'a amené à créer la séquence est nécessairement inférieur au dernier élément de la séquence précédente, puisqu'elle est croissante.

[invite35452583]

Je pense que la partie qui reste la plus floue est de prouver qu'avec cette construction je vais forcément avoir une séquence décroissante en remontant les listes.

En effet

Mais pour simplifier, je peux prendre une méthode un peu différente : au lieu de prendre l'élément de la liste précédente qui a précédé la création de la liste courante, je peux me contenter de prendre le dernier élément de la liste précédente au moment ou l'élément que je suis en train de considérer a été lu.

une petite version illustrée ?
eut-être inutile car je pense que l'on peut faire encore plus simple.
et que tout est là :

En fait, il faut prendre le "première" un peu plus littéralement : la première séquence de ma liste est 135. Du coup j'obtiens 1356 et 24.

Et mon "pas de bol" de tout à l'heure ne peut arriver.

[invite35452583]

eut-être inutile car je pense que l'on peut faire encore plus simple.

Oups, mon idée (que je n'ai pas donné) ne marche pas (je marche à reculons )
Encore plus preneur d'une version illustrée. A partir de :
4316527.10.89 par exemple.

[yat]

une petite version illustrée ?

Bon je vais essayer...

Voyons ce que ça donne avec les décimales de pi... j'attribue une ligne à chaque sous-séquence, et j'enfile au fur et à mesure. Voilà ce que ça donne pour les 16 premiers chiffres :

3141592653589793
3_4_59______9_9_
_1_1__26___8____
________5____7__
_________35_____
_______________3

Je commence par le 3 tout en bas (ligne 5). A moment ou il a été posé, il était forcément plus petit que le dernier chiffre de la ligne 4. Dans le cas contraire, ce 3 aurait été posé soit en ligne 4, soit dans une des lignes précédentes.
Même chose pour le 5, je remonte jusqu'au 5 de la ligne précédente, puis jusqu'au 6 de la ligne 2.
C'est là qu'on peut mettre en évidence que je me suis banané dans le dernier paragraphe de mon post précédent : la seule méthode qui fonctionne est bien la deuxième que j'ai donnée : on prend le dernier chiffre de la ligne 1 (posé avant le 6 sur lequel on se trouve), et on termine notre séquence décroissante : 96553.

Le problème dans le susdit dernier paragraphe et dans la première méthode que j'ai donnée, c'est que l'élément qui a précédé la création de la liste courante est plus petit que celui que je prends dans la même méthode. Et je me suis embrouillé en considérant que la suite devait être décroissante et en la prenant à l'envers...

eut-être inutile car je pense que l'on peut faire encore plus simple.

Je n'en doute pas une seconde

[yat]

Oups, mon idée (que je n'ai pas donné) ne marche pas (je marche à reculons )
Encore plus preneur d'une version illustrée. A partir de :
4316527.10.89 par exemple.

4316527.10.89
4__6__7.10.89
_3__5_______
__1__2______

La suite décroissante est 652.

[invite35452583]

Je commence par le 3 tout en bas (ligne 5). A moment ou il a été posé, il était forcément plus petit que le dernier chiffre de la ligne 4. Dans le cas contraire, ce 3 aurait été posé soit en ligne 4, soit dans une des lignes précédentes.
Même chose pour le 5, je remonte jusqu'au 5 de la ligne précédente, puis jusqu'au 6 de la ligne 2.

(Au fait les nombres sont censés être distincts mais bon ça ne change rien)
est-ce que je résume ta pensée en disant :
1)on transforme chaque nombre en boule-nombre que l'on va enfiler, dans l'ordre d'arrivée, sur des fils numérotés 1,2,...
2)chaque boule est enfilée sur le 1er fil qui ne contient que des nombres plus petits que lui (s'il est plus petit que tous ses prédécesseurs il se retrouve sur un nouveau fil)
A la fin on a x fils avec au moins une boule-nombre.
On crée ainsi une suite décroissante de longueur x :
on prend une boule-nombre n(x)du x-ème fil.
D'après b), la dernière boule-nombre du fil (x-1) au moment où n(x) est enfilé est plus grand que lui, on le note n(x-1)
De même, toujours d'après b) et tant que y>1, la dernière boule-nombre du fil (x-1) au moment où n(y) est enfilé est plus grand que lui, on le note n(y-1).
Ainsi les n(1),n(2)...n(x) se succédent dans la suite initiale et vérifie n(1)>n(2)>...>n(x), on a une sous-séquence décroissante de longueur x.
Bien joué
Reste à simplifier la conclusion numérique (avec la formule c'est plus simple maintenant)

[yat]

(Au fait les nombres sont censés être distincts mais bon ça ne change rien)

Distincts ? ( ) Bah... ça changerait quand même un peu tout... si les sous-séquences doivent être strictement monotones, plus moyen de faire une formule... d'une séquence d'un million de chiffres ne comprenant que des 4 et des 9, il va être difficile d'extraire une sous-séquence strictement croissante ou strictement décroissante de longueur supérieure à 2... Peut-être ai-je mal compris ce que tu veux dire ?

est-ce que je résume ta pensée en disant :
1)on transforme chaque nombre en boule-nombre que l'on va enfiler, dans l'ordre d'arrivée, sur des fils numérotés 1,2,...
2)chaque boule est enfilée sur le 1er fil qui ne contient que des nombres plus petits que lui (s'il est plus petit que tous ses prédécesseurs il se retrouve sur un nouveau fil)
A la fin on a x fils avec au moins une boule-nombre.
On crée ainsi une suite décroissante de longueur x :
on prend une boule-nombre n(x)du x-ème fil.
D'après b), la dernière boule-nombre du fil (x-1) au moment où n(x) est enfilé est plus grand que lui, on le note n(x-1)
De même, toujours d'après b) et tant que y>1, la dernière boule-nombre du fil (x-1) au moment où n(y) est enfilé est plus grand que lui, on le note n(y-1).
Ainsi les n(1),n(2)...n(x) se succédent dans la suite initiale et vérifie n(1)>n(2)>...>n(x), on a une sous-séquence décroissante de longueur x.

Oui, c'est bien ça ma solution

Reste à simplifier la conclusion numérique (avec la formule c'est plus simple maintenant)

C'est assez clair pour moi, mais j'ai énormément de mal à le formuler avec des mots

soit x la taille de la plus grande sous-séquence croissante, et y la taille de la sous-séquence décroissante, n la taille de la séquence complète. Il est immédiat que x*y>=n. Donc, en posant z le maximum de x et y, on a z>=x et z>=y donc z²>=n.

Après, il faut returner la chose, mais je n'arrive pas à faire plus explicite que dans mon premier post.

[invite35452583]

Distincts ? ( ) Bah... ça changerait quand même un peu tout... si les sous-séquences doivent être strictement monotones, plus moyen de faire une formule... d'une séquence d'un million de chiffres ne comprenant que des 4 et des 9, il va être difficile d'extraire une sous-séquence strictement croissante ou strictement décroissante de longueur supérieure à 2... Peut-être ai-je mal compris ce que tu veux dire ?Oui, c'est bien ça ma solutionC'est assez clair pour moi, mais j'ai énormément de mal à le formuler avec des mots

Si on prend des séquences monotones non strictement on a le droit aussi à des sous-séquences monotones non strictes.(loi n° 1987AZ21 art.45B)

soit x la taille de la plus grande sous-séquence croissante, et y la taille de la sous-séquence décroissante, n la taille de la séquence complète. Il est immédiat que x*y>=n. Donc, en posant z le maximum de x et y, on a z>=x et z>=y donc z²>=n.

Bon allez je termine
s'il y a uniquement des sous-séquences monotones de longueur inférieures à n, il y a au plus n fils de n boules-nombres donc au plus n² nombres. S'il y a au moins n²+1 nombres il y a donc une sous-séquence monotone de n+1 nombres.

Restent à montrer que l'on peut trouver une séquence de n² nombres sans sous-séquence de (n+1) nombres pour tout n.

[yat]

Si on prend des séquences monotones non strictement on a le droit aussi à des sous-séquences monotones non strictes.(loi n° 1987AZ21 art.45B)

J'ai pas tout capté, là... mais je crois que tu veux dire qu'on prend une séquence de départ dans laquelle tous les éléments sont différents, c'est ça ?

Restent à montrer que l'on peut trouver une séquence de n² nombres sans sous-séquence de (n+1) nombres pour tout n.

Encore par construction, alors... il suffit de donner une méthode de construction d'une telle séquence de longueur n². Alors je prends une suite strictement corissante de taille n², puis je la découpe en n tranches de n, et j'inverse l'ordre des tranches. On a donc n tranches croissantes, si une sous-séquence contient des éléments de plusieurs tranches, elle ne pourra pas être croissante. Inversement, si on construit une séquence décroissante on ne pourra prendre qu'un élément dans chaque tranche. Donc pour tout n, il existe une séquence de n² sans sous-séquence de (n+1) monotone.

[invite35452583]

Et comme je ne suis pas sûr d'avoir du temps après, deux autres méthodes :
la plus dans l'esprit des "tiroirs" (celle-là je l'avais trouvé tout seul)
Pour le nombre n(p) en position p,
on note c(p) la longueur de la plus longue sous-séquence croissante terminant par ce nombre,
on note d(p) la longueur de la plus longue sous-séquence décroissante terminant par ce nombre.
Exemple pour 3142 : 3->(1,1) 1->(1,2) 4->(2,1) 2->(2,2)
Les couples (c(p),d(p)) sont tous distincts, en effet :
soient p et q avec p<q,
si n(p)<n(q) on peut aggrandir la plus longue séquence croissante terminant par n(p) d'au moins un terme (n(q)) pour faire une sous-séquence croissante terminant par n(q) donc c(p)<c(q)
si n(p)>n(q), cette fois on a d(p)<d(q).
Les couples (a,b) avec 1<= a,b <=n sont en nombre n² donc s'il y a au moins n²+1 nombres dans la séquence au moins un des nombres de la séquence vérifie c(p)>=n+1 ou d(p)>=n+1.

par récurrence (celle-là je l'ai piquée)
le résultat est vrai pour n=2.
Supposons le vrai pour k=n.
Soit une séquence de longueur n²+1, on appelle majorant un terme de la séquence plus grand que tous ses successeurs, on appelle minorant un terme plus petit que tous ses successeurs.
Les majorants forment une sous-séquence décroissante, en effet : les successeurs de chaque terme de la sous-séquence sont plus petits par définition d'un majorant. de même les minorants forment une sous-séquence décroissante.
Si les majorants ou les minorants sont en nombre plus grands que n+1, c'est terminé.
Sinon, et en remarquant que le dernier terme de la séquence initiale est à la fois un majorant et un minorant, on a moins de 2n-1 majorants et minorants. On les retire, il reste une séquence de longueur d'au moins n²+1-(2n-1)=(n-1)²+1 éléments, on peut en extraire une sous-séquence monotone de longueur n. Le dernier terme n'étant ni un majorant ni un minorant de la séquence initiale on peut alors compléter cette sous-séquence de longueur n en une sous-séquence de longueur n+1.

reste à trouver cette séquence de longueur n².
EDIT : je viens de voir que yat propose quelque chose.

[invite35452583]

J'ai pas tout capté, là... mais je crois que tu veux dire qu'on prend une séquence de départ dans laquelle tous les éléments sont différents, c'est ça ?

Oui, il faut bien poser les règles à un moment.

Encore par construction, alors... il suffit de donner une méthode de construction d'une telle séquence de longueur n². Alors je prends une suite strictement corissante de taille n², puis je la découpe en n tranches de n, et j'inverse l'ordre des tranches. On a donc n tranches croissantes, si une sous-séquence contient des éléments de plusieurs tranches, elle ne pourra pas être croissante. Inversement, si on construit une séquence décroissante on ne pourra prendre qu'un élément dans chaque tranche. Donc pour tout n, il existe une séquence de n² sans sous-séquence de (n+1) monotone.

Et c'est donc fini.

[danyvio]

Scrongneugneu, c'est le genre de problème que se posaient les ingérieurs informaticiens des années 50 - 60 qui concoctaient des programmes de tri d'informations sur bande magnétique, non ?

[invite35452583]

Scrongneugneu, c'est le genre de problème que se posaient les ingérieurs informaticiens des années 50 - 60 qui concoctaient des programmes de tri d'informations sur bande magnétique, non ?

Bonjour,
c'est bien possible mais je ne connais pas l'histoire de ce problème, je l'ai trouvé dans un livre de mathématiques "parallèles".
Cordialement