suite sans répétitions

[invite35452583]

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,

C'est la même que j'avais (décalée d'un cran+pas bien attentif donc pas vu immédiatement)
je suis vraiment impressionné : quand je me suis attaqué à ce problème, il m'a fallu revenir plusieurs fois dessus pour trouver.

Par contre :

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

Ce n'est pas tout à fait complet.
Ce que tu as plus ou moins montré (tous les arguments y sont, c'est l'essentiel) c'est si une suite de longueur 3k se répète 3 fois alors on a
01n(3h) 01n(3(h+1))... 01n(3h+3x3k) (n(i)=nombre à la i-ème place)

mais n(3h)n(3(h+1))...n(3h+3x3k)=n( h)n(h+1)...n(h+3k) et on a une répétition de longueur k.

Donc la longueur minimale d'une telle répétition ne peut être un multiple de 3.

Maintenant reste à régler le cas des séquences de longueur k non multiple de 3 pour lesquelles cet argument ne fonctionne plus.
Ceci dit le plus difficile est fait.
fin de la réponse plus tard par moi ou un autre. J'en donnerai un autre exemple mais sans démo.
-----

[invité576543]

Maintenant reste à régler le cas des séquences de longueur k non multiple de 3 pour lesquelles cet argument ne fonctionne plus.

Belle bourde de ma part... Du coup, c'est moi qui ne vois plus pourquoi ça marche J'va réfléchir. EDIT: La réponse est dans la démo de Yat...

Cordialement,

[invite35452583]

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

Bravo Yat pour la démo
C'est ce qui manque (j n'avais vu ce post tout à l'heure)
c'est un peu succinct aussi (en plus développé mais simplifié) :
on a u(n+2m)=u(n+m)=u(n) car longueur de la séquence =m.
Ici m n'est pas un multiple de 3 donc un parmi n,n+m et n+2m est congru à1 moulo 3 et son "n" vaut 0, un autre parmi ces trois là est congru à 2 modulo 3 et son "n" vaut 1. Contradiction.

Une autre suite qui fonctionne (c'est historiquement la 1ère trouvée) est construite ainsi
0
01 (1 est l'opposé de 0)
0110 (10 est l'opposé de 01)
01101001 (1001 est l'opposé de 0110)
et on ajopute ainsi à chaque fois l'"opposé"

Fort de ces exemples (dont un démontré), on construit une situation échiquéenne telle que l'on passe d'une position sur l'échiquier à la même par deux voies possibles sans autre redondance (la "0" et la "1") et à jouer "0" ou "1" selon ce que la suite "dit".

[invité576543]

Une autre suite qui fonctionne (c'est historiquement la 1ère trouvée) est construite ainsi
0
01 (1 est l'opposé de 0)
0110 (10 est l'opposé de 01)
01101001 (1001 est l'opposé de 0110)
et on ajopute ainsi à chaque fois l'"opposé"

Ca n'aurais pas un rapport avec la courbe de Peano, en prenant 0 = demi-tour par la droite, et 1= demi-tour par la gauche?

Cordialement,