Répondre à la discussion
Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 30 sur 34

suite sans répétitions



  1. #1
    homotopie

    Exclamation suite sans répétitions


    ------

    J'espère qu'elle n'a pas déjà été posée (pas le courage de revoir tous les topics). je préviens qu'elle n'est pas du genre facile. (pléonasme)
    motivation : une règle supplémentaire au jeu d'échecs a été ajoutée (quand?? pas hier en tout cas) aux règles initiales afin d'éviter les parties infinies. Cette règle dit que si la même séquence de coups (donc finie) est répété trois fois alors la partie est nulle. Cette règle atteint-elle son objectif? (La "règle des 50 coups", elle, l'atteint)
    Simplifions et changeons un peu les données du problème (car tout le monde ne joue pas aux échecs) :
    peut-on définir une suite de 0 et de 1 telle qu'aucune séquence (quelque soit la longueur!) ne soiot répétée 3 fois ?
    Contre-exemples :
    000... (perdu)
    010110110110 ... (perdu)
    Bon courage

    -----

  2. #2
    homotopie

    Re : suite sans répétitions

    J'avais oublié de m'abonner

  3. #3
    g_h

    Re : suite sans répétitions

    Citation Envoyé par homotopie Voir le message
    Contre-exemples :
    000... (perdu)
    010110110110 ... (perdu)
    Bon courage

    Salut,

    Juste, pour le 2ème, on a 0 101 101 101 10 donc on avait perdu avant

    Je vais me creuser la tête... je sens que ça va faire mal !

  4. #4
    yat

    Re : suite sans répétitions

    Petite précision : c'est trois fois de suite, ou bien simplement trois fois ?

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

    Re : suite sans répétitions

    Citation Envoyé par yat Voir le message
    Petite précision : c'est trois fois de suite, ou bien simplement trois fois ?
    Je ne suis pas sûr de bien comprendre la question. Mais celle-ci est de savoir si la répétition doit se faire dès le début alors non cf 2ème exemple.

    Citation Envoyé par yat
    Juste, pour le 2ème, on a 0 101 101 101 10 donc on avait perdu avant
    J'ai honte

  7. #6
    chag

    Re : suite sans répétitions

    bonjour,

    Citation Envoyé par yat Voir le message
    Petite précision : c'est trois fois de suite, ou bien simplement trois fois ?
    +1

    parce que si 0 tout seul (ou 1 tout seul ) peut être considéré comme une séquence et que la règle de non répétition ne précise pas "3 fois de suite", il n'y a aucune suite qui la respecte !

    ex : 10011011 donc perdu.....

  8. #7
    Gwyddon

    Re : suite sans répétitions

    Je reformule la question de yat :

    101 1 101 101 1 par exemple entraîne-t'il une partie nulle ?
    A quitté FuturaSciences. Merci de ne PAS me contacter par MP.

  9. #8
    g_h

    Re : suite sans répétitions

    Citation Envoyé par Gwyddon Voir le message
    Je reformule la question de yat :

    101 1 101 101 1 par exemple entraîne-t'il une partie nulle ?
    Comme le dit chag, aucune suite ne pourrait respecter cette règle. Il suffit de prendre la séquence "1" (on ne peut pas écrire un même élément plus de 3 fois) ou "10" (la suite doit alors devenir constante) pour s'en convaincre !

  10. #9
    Gwyddon

    Re : suite sans répétitions

    Tout à fait d'accord, je n'ai que reformulé

    C'est donc 3 fois de suite.
    A quitté FuturaSciences. Merci de ne PAS me contacter par MP.

  11. #10
    yat

    Re : suite sans répétitions

    Ok... donc la réponse à la question initiale est : OUI.

    Explication : homotopie l'a dit dans le fil sur les échecs


  12. #11
    homotopie

    Re : suite sans répétitions

    Oui, bien sûr c'est trois fois de suite (c'est terrible quand c'est évident pour soi on a toujours du mal à ne pas saisir que cela ne l'est pas pour les autres) milles désoles pour ce manque de précision.

  13. #12
    homotopie

    Re : suite sans répétitions

    Citation Envoyé par yat Voir le message
    Ok... donc la réponse à la question initiale est : OUI.
    Réponse acceptée
    Citation Envoyé par yat Voir le message

    Explication : homotopie l'a dit dans le fil sur les échecs
    Justification refusée

  14. #13
    invité576543
    Invité

    Re : suite sans répétitions

    Proposition très "intuitive", le nombre d'or en binaire. (Intuition basée sur les suites pseudo-répétitives obtenues avec les fractions continues, et le fait que le nombre d'or est le nombre avec les périodes de pseudo-répétition les plus courtes...)

    Cordialement,

  15. #14
    yat

    Re : suite sans répétitions

    Citation Envoyé par mmy Voir le message
    Proposition très "intuitive", le nombre d'or en binaire.
    1,100111100...

  16. #15
    invité576543
    Invité

    Re : suite sans répétitions

    J'ai la flemme de programmer! Merci, yat!

    Je pense quand même que les fractions continues sont une bonne piste...

    Peux-tu essayer des variantes genre 1/(2+phi) ou 1/(3+phi), juste pour casser les petites séquences?

    Cdlt,

  17. #16
    invité576543
    Invité

    Re : suite sans répétitions

    Autre proposition,

    La suite définie récursivement comme

    sn = 01s001s101s201s301s401...

    soit au début

    010011010010011010011

    Cordialement,

    Promis, après ça je réfléchis avant de proposer quelque chose...
    Dernière modification par invité576543 ; 09/01/2007 à 16h16.

  18. #17
    yat

    Re : suite sans répétitions

    Citation Envoyé par mmy Voir le message
    J'ai la flemme de programmer! Merci, yat!
    Programmer ?
    Bah dans la calculette windows, 5, racine, +, 1, /, 2, *, 16384, bin. C'était juste pour vérifier les premières décimales.
    Citation Envoyé par mmy Voir le message
    Je pense quand même que les fractions continues sont une bonne piste...
    Personnellement le lien entre les propriétés de la séquence et celles du nombre qu'e,,e représente en binaire me parait un peu douteux...
    Citation Envoyé par mmy Voir le message
    Peux-tu essayer des variantes genre 1/(2+phi) ou 1/(3+phi), juste pour casser les petites séquences?
    Ok, chef, mais juste les premières décimales, flemme de programmer ! Mais ça ne marche pas, on a trois zéros dans le premier, et trois 1 dans le deuxième.

  19. #18
    yat

    Re : suite sans répétitions

    Citation Envoyé par mmy Voir le message
    La suite définie récursivement comme

    sn = 01s001s101s201s301s401...

    soit au début

    010011010010011010011
    Je ne comprends pas la définition de ta suite.

    J'ai interprété comme ça :
    s0 = 0
    s1 = 01s0 = 010
    s2 = 01s001s1 = 01001010

    Donc déjà, c'est pas bon. Comment tu la définis, exatement ?

  20. #19
    invité576543
    Invité

    Re : suite sans répétitions

    Citation Envoyé par yat Voir le message
    Personnellement le lien entre les propriétés de la séquence et celles du nombre qu'e,,e représente en binaire me parait un peu douteux...
    Il y a une relation entre le développement en fractions continues et certaines répétitions. Une fraction rationnelle a un développement en fraction continue nulle à partir d'un certain rang, et les binales (ou décimales) sont répétitives. Si tu prends une fraction continue avec un grand nombre, genre (7, 1000000, ...) la répétition du motif de 7 (142857 en décimal) va être une "pseudo-période", avec un décalage approximativement tout les 1000000 décimales.

    Ok, chef, mais juste les premières décimales, flemme de programmer ! Mais ça ne marche pas, on a trois zéros dans le premier, et trois 1 dans le deuxième.
    Piste pas terrible, donc...

    Cordialement,

  21. #20
    invité576543
    Invité

    Re : suite sans répétitions

    Citation Envoyé par yat Voir le message
    Donc déjà, c'est pas bon.
    Pourquoi pas bon? Je n'ai peut-être pas bien compris la règle alors...

    Cdlt,

  22. #21
    yat

    Re : suite sans répétitions

    Citation Envoyé par mmy Voir le message
    Pourquoi pas bon? Je n'ai peut-être pas bien compris la règle alors...

    Cdlt,
    Non, non, je veux dire que ma compréhension de ta suite est pas bonne, puisque je n'obtiens pas la même chose que toi.

  23. #22
    invité576543
    Invité

    Re : suite sans répétitions

    Définition de la suite:

    En indiçant à partir de 1, tu écris la position n en base 3, et tu mets 0 si le chiffre non nul de poids le plus faible est 1, et 1 s'il vaut 2.

    La suite se présente au début comme ça, avec la suite noire, la suite rouge, la suite bleue, toutes égales à (01)ω

    010011010010011011010

    Cdlt,

  24. #23
    homotopie

    Re : suite sans répétitions

    L'idée de mmy ne me semble pas a priori mauvaise, je ne sais pas si elle est valide, je sens la démo assez hard quand même.

  25. #24
    invité576543
    Invité

    Re : suite sans répétitions

    Pas trop le temps pour faire les choses bien, mais y'a peut-être une démo comme suit.

    Les répétitions de séquences de longeur 1 ou 2 s'éliminent à vue.

    Si la séquence est de longueur au moins 3, il y a nécessairement une sous-séquence pour les positions égales à 0 modulo 3, et on récurre sur cette sous-suite...

    Cordialement,

  26. #25
    yat

    Re : suite sans répétitions



    Bon, les deux débuts de suite que tu indiques dans les deux posts ne sont pas les mêmes. Mais avec tes dernières explications j'obtiens une suite dont le début coïncide avec la tienne (la dernière). Par contre je ne saisis pas bien (en supposant que j'ai compris la construction de la suite) l'intérêt d'intercaler des 01 entre tous les éléments... il me semble que la suite que tu proposes respectera les conditions du problème si et seulement si la suite sans les 01 la respecte.

    EDIT : Ah non, en fait je viens de comprendre... l'intérêt est précisément cette équivalence entre la suite et la suite dans laquelle on a intercalé les 01... d'ou la construction récursive.
    Dernière modification par yat ; 09/01/2007 à 17h26.

  27. #26
    invité576543
    Invité

    Re : suite sans répétitions

    Citation Envoyé par yat Voir le message
    il me semble que la suite que tu proposes respectera les conditions du problème si et seulement si la suite sans les 01 la respecte.
    Tout à fait! Mais c'est la même

    La suite est identique à celle obtenue en ne prenant que les positions multiple de 3... (C'est exactement la description dans le message où je l'introduis.)

    La propriété que tu cites donne une magnifique glissade à l'infini...

    Cdlt,

  28. #27
    invité576543
    Invité

    Re : suite sans répétitions

    Je crois que la démo est solide et pas hard du tout. QED, non?

    Cordialement,

  29. #28
    yat

    Re : suite sans répétitions

    Citation Envoyé par mmy Voir le message
    Tout à fait! Mais c'est la même
    Oui, en effet, c'est ce qui fait le miracle de la chose. On a donc une solution, là...

    Pour la démo (j'essaye de développer un peu, parce que la tienne est extrêmement succinte ), en gros, il faut démontrer que si une suite U respecte la propriété, alors la suite V définie par V3n=0, V3n+1=1, V3n+2=Un, la respecte aussi. On peut commencer par constater que s'il y avait une séquence répétée trois fois dans V, cette séquence serait de taille multiple de 3 (dans le cas contraire, il y aurait forcément une des trois occurences qui commencerait par un 1 et une qui commencerait par un 0). Ensuite, il est évident que pour voir une telle séquence, il faut que les V3n+2 constituent eux aussi une séquence répétée trois fois. En d'autres termes, si V ne respecte pas la propriété, U ne la respecte pas non plus, et la contraposée nous dit donc que si U respecte la propriété, V la respecte aussi.

    Après, j'ai un peu peur de faire un raisonnement maladroit, mais je pense qu'en considérant des suites de longueurs finies, on peut partir d'une suite de taille 2 dont les éléments sont 0 et 1, et de faire tendre récursivement sa longueur vers l'infini en conservant la propriété. Ca te semble rigoureux ?

    et homotopie, tu avais une autre solution ?

  30. #29
    yat

    Re : suite sans répétitions

    Citation Envoyé par mmy Voir le message
    Je crois que la démo est solide et pas hard du tout. QED, non?
    Oui, je pense, même si c'est vraiment résumé à l'extrème (pour les esprits un peu lents comme moi, il la relire plein de fois pour comprendre ).

    Chapeau, en tout cas. Voilà une solution bien élégante.

  31. #30
    invité576543
    Invité

    Re : suite sans répétitions

    Ma démo par récurrence, un peu plus développée:

    Soit s la longueur de la séquence répétée.

    On procède par récurrence sur p, 3p étant la plus petite puissance de 3 strictement supérieure à s:

    Si p=1, s égale 1 ou 2;

    Les séquences de longueur 1 sont éliminées, il y nécessairement 01 dans toute séquence de 3 successives.

    Les séquences de longueur 2 sont soit 01x01x, 1x01x0 ou x01x01, aucun cas possible de répétition.

    Si p>1

    Alors s>=3, et la sous-suite extraite des u3n contient nécessairement une répétition, et par récurrence ce n'est pas possible.

    Cordialement,

Page 1 sur 2 1 DernièreDernière

Discussions similaires

  1. Permutation avec répétitions ?
    Par LicenceXP dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 27/03/2012, 18h17
  2. Comment démontrer qu'une suite est une suite géométrique de raison b?
    Par Tounsia dans le forum Mathématiques du collège et du lycée
    Réponses: 9
    Dernier message: 22/09/2007, 19h45
  3. egalité de suite (2 façons d'exprimer la même suite)[1ere S]
    Par lila23 dans le forum Mathématiques du collège et du lycée
    Réponses: 8
    Dernier message: 21/05/2006, 10h13
  4. Choix d’une station de soudage /suite/ soudure sans plomb
    Par frankie dans le forum Électronique
    Réponses: 1
    Dernier message: 02/11/2004, 17h56
  5. une suite sans nom!
    Par azzedine dans le forum Archives
    Réponses: 9
    Dernier message: 23/11/2003, 16h02