suite sans répétitions

[invite35452583]

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
-----

[invite35452583]

J'avais oublié de m'abonner

[g_h]

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 !

[yat]

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

[A voir en vidéo sur Futura]

[invite35452583]

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.

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

J'ai honte

[invite2c79b73d]

bonjour,

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.....

[Gwyddon]

Je reformule la question de yat :

101 1 101 101 1 par exemple entraîne-t'il une partie nulle ?

[g_h]

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 !

[Gwyddon]

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

C'est donc 3 fois de suite.

[yat]

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

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

[invite35452583]

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.

[invite35452583]

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

Réponse acceptée

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

Justification refusée

[invité576543]

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,

[yat]

Proposition très "intuitive", le nombre d'or en binaire.

1,100111100...

[invité576543]

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,

[invité576543]

Autre proposition,

La suite définie récursivement comme

s_n = 01s₀01s₁01s₂01s₃01s₄01...

soit au début

010011010010011010011

Cordialement,

Promis, après ça je réfléchis avant de proposer quelque chose...

[yat]

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.

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...

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.

[yat]

La suite définie récursivement comme

s_n = 01s₀01s₁01s₂01s₃01s₄01...

soit au début

010011010010011010011

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

J'ai interprété comme ça :
s₀ = 0
s₁ = 01s₀ = 010
s₂ = 01s₀01s₁ = 01001010

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

[invité576543]

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,

[invité576543]

Donc déjà, c'est pas bon.

Pourquoi pas bon? Je n'ai peut-être pas bien compris la règle alors...

Cdlt,

[yat]

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.

[invité576543]

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,

[invite35452583]

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.

[invité576543]

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,

[yat]

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.

[invité576543]

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,

[invité576543]

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

Cordialement,

[yat]

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 V_3n=0, V_3n+1=1, V_3n+2=U_n, 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 V_3n+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 ?

[yat]

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.

[invité576543]

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, 3^p é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 u_3n contient nécessairement une répétition, et par récurrence ce n'est pas possible.

Cordialement,