Partie d'échec infinie

[Nightmare]

Salut à tous,

un problème lié aux échecs et à la règle du draw lorsqu'une série de mouvement est répétée 3 fois :

Existe-t-il une suite binaire infinie dans laquelle aucune sous-suite finie ne se répète trois fois de suite?

Bonne réflexion.
:happy3:

[Mathusalem]

Si je connaissais les définitions, est-ce que je pourrais m'en sortir, ou est-ce que c'est trop pointu comme question au niveau du bagage à avoir ?

[Nightmare]

Salut Mathusalem,

de quelle définition parles-tu?

Si c'est suite binaire qui te dérange, il s'agit simplement d'une suite de 0 et de 1.

Le problème n'est pas difficile sinon.

[Mathusalem]

Ok. J'y réfléchis. Mais pourquoi cette question a-t-elle un lien avec le draw en échec ?

[Nightmare]

En assimilant un mouvement à une suite binaire, la question revient à se demander s'il existe une suite infinie de mouvements qui ne contienne aucune série de 3 mouvements qui se répète, autrement dit une partie infinie d'échec sans draw.

[beagle]

Il y a déjà eu un fil sur cette question.
Il n' y avait pas de démonstration, mais avec un nombre fini de pièces sur un ensemble fini de cases,
jouer à l'infini est impossible sans répétition de la position.
la position à l'instant t est définie par
64 cases où tu mets les pièces, ou un ensemble de ces pièces
supposons que l'on ne tienne pas compte des règles du jeu d'échecs, on met les pièces n'importe où,
alors avec toutes les pièces dans les 64 cases
avec toutes les pièces moins une dans les 64 cases
moins deux cans 64 cases
..
les deux rois dans 64 cases , c'est fini
et ce dénombrement est supérieur au nombre possible autorisé par les règles.

bon, c'est un peu plus compliqué que cela car il y a des régénérations de pièces possibles par promotion, mais la finitude est la mème car ne générant pas de pions on ne peut générer de pièces à l'infini,
qui plus est ce que je raconte n'est pas nécessaire car la génération de pièce se transforme en pièces existantes qui répétent donc la position par rapport aux dénombrement déjà fini précédent qui surcote.

[beagle]

pour la promotion,
alors recommençons le dénombrement avec
les 32 pièces + les ensembles de promotion possibles
au maxi c'est 15 dames, ou 14 dames + un fou ..etc...
c'est un nombre de combis limité

et on recommence à placer tout ce monde dans les 64 cases,
c'est un nombre fini de combis possibles,
et ce nombre surcote les possibilités réelles du jeu

[Nightmare]

Salut beagle,

en fait, j'ai posé la question avec le suites plutôt que directement avec les échecs car effectivement, les règles des échecs imposent qu'il existe des positions qui ne peuvent pas être obtenues dans une partie.

En particulier, si une suite demandée dans mon problème existe (edit : remarque supprimée (spoil)), il est possible qu'elle ne corresponde pas à une partie d'échec réalisable.

[beagle]

Salut beagle,

en fait, j'ai posé la question avec le suites plutôt que directement avec les échecs car effectivement, les règles des échecs imposent qu'il existe des positions qui ne peuvent pas être obtenues dans une partie.

En particulier, si une suite demandée dans mon problème existe (ce qui est le cas, autant cracher le morceau pour ceux qui essayent de prouver que ça n'existe pas), il est possible qu'elle ne corresponde pas à une partie d'échec réalisable.

alors cela ce n'est pas vraiment le problème des règles du jeu d'échecs,
c'est le problème que la suite n'est pas comparable à une position donnée,
parce que mème si les pièces vont n'importe où et sont supprimées n'importe comment,
c'est le fait de revenir à une position qui crée la finitude.

[Nightmare]

Oui, d'où le fait qu'encore une fois, je ne souhaite pas une réponse liée aux échecs mais entièrement relative à ma question qui, elle, est purement analytique.

[Imod]

Je ne suis pas sûr que tu as compris la question Beagle , Nightmare faisait juste un parallèle avec le jeu d'échec .

Le problème est : peut-on éviter 11001001001011011...

Je suis presque sûr que non , après il faut trouver le bon angle d'attaque :zen:

Imod

[beagle]

Oui, d'où le fait qu'encore une fois, je ne souhaite pas une réponse liée aux échecs mais entièrement relative à ma question qui, elle, est purement analytique.

OK, alors c'est quoi une sous-suite finie de 0 et 1?

[Nightmare]

J'ai spoilée la réponse dans un de mes posts précédent Imod, j'ai supprimée ma remarque en espérant que tu ne l'aies pas lue, pour ton plaisir.

[Nightmare]

OK, alors c'est quoi une sous-suite finie de 0 et 1?

Si le terme te dérange, remplace le par "bloc".

Autrement dit, dans la séquence binaire, il faudrait qu'aucun bloc ne se répète trois fois de suite. Cf post de Imod.

Un bloc pouvant être de longueur quelconque, en particulier la suite, si elle existe, ne devra pas comporter trois fois de suite le même terme.

[beagle]

Si le terme te dérange, remplace le par "bloc".

Autrement dit, dans la séquence binaire, il faudrait qu'aucun bloc ne se répète trois fois de suite. Cf post de Imod.

Un bloc pouvant être de longueur quelconque, en particulier la suite, si elle existe, ne devra pas comporter trois fois de suite le même terme.

par exemple un bloc de un seul 0 ou un seul 1?

[nodjim]

Pour autant que je me souvienne d'un problème similaire déja posé, ce n'est pas possible sans doublement d'une sous suite d'au moins 2 chiffres (ou 3 chiffres ?). Il n'est pas certain du tout qu'on aboutisse aux mêmes conclusions avec le triplement.
Il va falloir tout de même, d'emblée, éviter le triple 0 ou le triple 1, sauf si on assouplit avec une sous suite de 2 ou 3 chiffres minimum.

[Nightmare]

par exemple un bloc de un seul 0 ou un seul 1?

Tout à fait.

[Mathusalem]

J'imagine que suites qui marchent pas :

00010.....
101010....
110011001100

etc.

J'essaye de trouver une construction qui permettent d'éviter cela, mais c'est chaud de s'assurer que la construction évite les triplets.

[Nightmare]

Il va falloir tout de même, d'emblée, éviter le triple 0 ou le triple 1, sauf si on assouplit avec une sous suite de 2 ou 3 chiffres minimum.

Oui, comme précisé ci-dessus à Beagle, on cherche une suite telle que tout bloc de longueur quelconque - en particulier de longueur 1 - ne soit répété 3 fois de suite.

[Imod]

Bon j'ai trouvé en trichant un peu ( en proposant le début à l'OEIS ) . La suite existe bien , elle s'appelle la suite de Prouhet-Thue-Morse .

Assez bluffant :zen:

Imod