Répondre à la discussion
Affichage des résultats 1 à 17 sur 17

séquences monotones mais distrayantes



  1. #1
    homotopie

    Cool séquences monotones mais distrayantes


    ------

    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 ?

    -----

  2. #2
    homotopie

    Re : séquences monotones mais distrayantes

    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.

  3. #3
    yat

    Re : séquences monotones mais distrayantes

    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 !

  4. #4
    homotopie

    Re : séquences monotones mais distrayantes

    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)
    Citation Envoyé par yat
    à 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) :
    Citation Envoyé par yat
    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.

  5. A voir en vidéo sur Futura
  6. #5
    yat

    Re : séquences monotones mais distrayantes

    Citation Envoyé par homotopie Voir le message
    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.
    Citation Envoyé par homotopie Voir le message
    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.
    Citation Envoyé par homotopie Voir le message
    Ce que j'ai mis en gras c'est bien "croissantes" qu'il faut lire, non ?
    En effet. Désolé pour le lapsus.
    Citation Envoyé par homotopie Voir le message
    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.

  7. #6
    homotopie

    Re : séquences monotones mais distrayantes

    Citation Envoyé par yat Voir le message
    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
    Citation Envoyé par yat
    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à :
    Citation Envoyé par yat
    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.

  8. #7
    homotopie

    Re : séquences monotones mais distrayantes

    Citation Envoyé par homotopie Voir le message
    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.

  9. #8
    yat

    Re : séquences monotones mais distrayantes

    Citation Envoyé par homotopie Voir le message
    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...
    Citation Envoyé par homotopie Voir le message
    eut-être inutile car je pense que l'on peut faire encore plus simple.
    Je n'en doute pas une seconde

  10. #9
    yat

    Re : séquences monotones mais distrayantes

    Citation Envoyé par homotopie Voir le message
    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.

  11. #10
    homotopie

    Re : séquences monotones mais distrayantes

    Citation Envoyé par yat Voir le message
    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)

  12. #11
    yat

    Re : séquences monotones mais distrayantes

    Citation Envoyé par homotopie Voir le message

    (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 ?
    Citation Envoyé par homotopie Voir le message
    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
    Citation Envoyé par homotopie Voir le message
    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.

  13. #12
    homotopie

    Re : séquences monotones mais distrayantes

    Citation Envoyé par yat Voir le message
    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)
    Citation Envoyé par yat Voir le message
    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.

  14. #13
    yat

    Re : séquences monotones mais distrayantes

    Citation Envoyé par homotopie Voir le message
    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 ?
    Citation Envoyé par homotopie Voir le message
    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.

  15. #14
    homotopie

    Re : séquences monotones mais distrayantes

    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.

  16. #15
    homotopie

    Re : séquences monotones mais distrayantes

    Citation Envoyé par yat Voir le message
    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.

    Citation Envoyé par yat Voir le message
    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.

  17. #16
    danyvio

    Re : séquences monotones mais distrayantes

    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 ?
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

  18. #17
    homotopie

    Re : séquences monotones mais distrayantes

    Citation Envoyé par danyvio Voir le message
    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

Discussions similaires

  1. les séquences
    Par ririri dans le forum Biologie
    Réponses: 18
    Dernier message: 29/05/2007, 14h50
  2. alignement de séquences
    Par calypso26 dans le forum Biologie
    Réponses: 3
    Dernier message: 09/12/2006, 15h21
  3. convergence des suites monotones
    Par fany93 dans le forum Mathématiques du collège et du lycée
    Réponses: 17
    Dernier message: 28/09/2006, 21h35
  4. Sequences répétées
    Par Barbanath dans le forum Biologie
    Réponses: 2
    Dernier message: 25/05/2006, 11h32
  5. Logiciel Anagène : séquences
    Par dj_titeuf dans le forum Biologie
    Réponses: 1
    Dernier message: 30/05/2005, 18h20