Mots binaires, dénombrement

[redwolf]

Bonjour, voici un petit problème que je n'arrive pas à résoudre :

Parmi tous les mots binaires cycliques de longueur 2^n (cyclique signifiant que le dernier chiffre est suivi du premier) combien y en a-t-il qui contiennent tous les mots de longueur n ?

La réponse semble être 2^(2^(n-1)), mais je n'arrive pas à le démontrer :triste:

Merci pour votre aide !

[moroccan]

Je ne trouve as du tout claire la définition que tu donnes aux nombres cycliques.. Peux-tu réexpliquer, en donnant des exemples éventuellement?

[memphisto]

Je suis du meme avis.

[redwolf]

Bonsoir. Voici quelques précisions sur mon énoncé :

Un mot binaire est une suite de 0 et de 1. Exemple : 00010111 est un mot binaire de longueur 8.
Cyclique veut dire qu'il faut considérer que le dernier chiffre est suivi du premier, comme si on avait écrit ce mot le long d'un cercle. Ainsi, le mot ci-dessus contient les mots 000 ; 001 ; 010 ; 101 ; 011 ; 111 (je les mets dans l'ordre en allant de gauche à droite) mais aussi 110 et 100.

Au passage, cet exemple fait partie des mots cycliques de longueur 8 qui contiennent tous les mots possibles de longueur 3. C'est donc un de ceux qu'il faut dénombrer pour n=3.

Merci pour votre intérêt, et bonne reflexion.

[redwolf]

Bonsoir.

Oui, c'est une bonne piste. Tu montres en quelque sorte deux solutions "primitives", et tu obtiens toutes les autres par permutation circulaire.

Mais si la réponse que je suggère est correcte, pour n=4, il y aura 256 solutions. Comme par permutation circulaire, on en obtient 16 à partir d'une solution "primitive", il faudra quand même exhiber 16 solutions primitives différentes.

Et pour n=5, 65536 solutions groupées par 32, ça fait tout de même 2048 solutions "primitives" à dénicher. Et ça, il faut un moyen pour les obtenir toutes...

Je l'ai vérifié à la main pour n=4 et n=5 (eh oui, j'ai écrit les 2048 solutions "primitives" et je me suis assuré qu'elles étaient bien différentes !). Mais on ne peut guère aller plus loin à la main, et je cherche un argument théorique qui pourrait enfin rendre tout mon travail précédent inutile !!

Bonne nuit,

Redwolf