Trouvez moi un bon mot...

[Ben314]

Salut,
Je suis retombé sur un bouquin d'énigme que j'avais pas ouvert depuis fort longtemps. En voici une :

A l'aide des lettres A,B,C on veut former des mots, mais certaines suites de 2 lettres ou plus sont interdites.
Par contre on sait que deux suites de lettres interdites n'ont jamais la même longueur : il y a au plus une suite de deux lettres interdite, au plus une suite de trois lettres interdite, etc...
Montrer que l'on peut former de "bon" mots (i.e. ne contenant aucune suite interdite) de longueur arbitrairement grande.

[nodgim]

Ce n'est pas facile à compter, mais il me semble que pour une suite de n lettres, le nombre de mots interdits de 2, 3 ,....n lettres est inférieur à 3 ^n.

[FLBP]

Salut,
Si on exagère le nombre de mots qui sont "bloqués" par les mots interdits, en supposant que ces derniers sont formés de lettres disjointes, et qu'ils sont disjoints deux à deux :
On peut les compter plus facilement, pour un mot de lettres plus grand que 1, on a pour un mot interdit de :
lettres : mot "bloqué"
lettres : mots "bloqués"

lettres : mots "bloqués"
Ainsi on a :

Où les est le nombre de mots total.

[nodgim]

Non hélas, pour 2 lettres par exemple, c'est bien plus que 3^(n-2) mots interdits.

[Ben314]

J'ai pas trop réfléchi à la question (*) mais je pense comme vous que le dénombrement risque d'être la bonne solution.
Par contre, effectivement, à priori, parmi les mots de lettres, des qui ne sont "pas bon" car contenant une suite interdite de longueur , il me semble qu'il y en a et pas (la suite interdite, c'est soit les premières lettre -> 3 possibilité pour la dernière, soit dernières -> 3 possibilités pour la première), non ?

(*) Le bouquin c'est un recueil de truc d'olympiades et autres donc l'énoncé est forcément correct et en plus y'a les solutions, donc si je trouve pas, ben j'aurais qu'à tricher et aller regarder la soluce (et si doraki était encore là, j'aurais ajouté qu'après avoir lu la soluce, j'aurais sans vergogne affirmé que c'était trivial...)

[aviateur]

Bonjour
Pour je désigne par u(n) le nombre de mots interdits.
On considère un mot M de longueur n+1.
Les n premières lettres de M forment un mot de longueur n et les n dernières un mot de longueur n.
Si un mot est interdit dans M il est alors
- soit interdit dans (et de longueur <=n) il y en u(n) possibles en tout
- soit interdit dans (et de longueur <=n) il y en u(n) possibles en tout (mais ce n'est pas exclusif au premier cas)
-soit interdit dans n+1 (donc de longueur n+1) et il y 1 seul possible d'après les hypothèses.
On en déduit que
Soit alors la suite w(n) définie par et
c'est un suite majorante de u(n) et un calcul simple donne
Un autre calcul simple montre que w(n)<3^n pour tout n>=2.

[Ben314]

Si un mot est interdit dans M il est alors
- soit interdit dans (et de longueur <=n) il y en u(n) possibles en tout

Ca serait pas plutôt ?
(partant d'un mot M1 pas bon de longueur n, pour obtenir M, y'a 3 possibilité pour la lettre qu'on ajoute à la fin)

[aviateur]

9a ne marche pas? Ou bien je ne suis pas clair ou bien erreur?
Si les x_i pris dans {A,B,C}
et parmi toutes les possibilités il y en a un nombre u(n) interdit.
et parmi toutes les possibilité de faire M_2 il y en a un nombre u(n) interdit.
Dans M un mot interdit de longueur <= ou égal à n est dans ou (non exclisif) .
Donc le nombre de mots interdits dans M et de longueur <= à n est au plus 2 u(n).
Il reste encore un seul mot interdit dans M non comptabilisé c'est celui de longueur n+1.
En tout au plus 2u(n)+1 mot interdits : u(n+1)<=2u(n)+1

[Ben314]

Si la séquence interdite de 2 lettres est AB et celle de 3 lettre est CCC alors
- Le seul mot pas bon de 2 lettres est AB => u(2)=1
- Les mots pas bon de 3 lettres sont ABA, ABB, ABC, AAB, BAB, CAB, CCC => u(3)=7
donc u(3) = 2x3xu(2) + 1 > 2.u(2)+1

[aviateur]

Oui, ce n'est pas cela.
Ce qu'il se passe c'est que pour un mot de longueur n+1 comme je l'ai fait ci-dessus mais en corrigeant;
il faut comprendre que j'ai compté 2 fois les mots de longueur n-1 qui sont à la fois dans les deux cas mots
et
Donc erreur j'obtiens que u(n+1) est majoré par

[aviateur]

Si le raisonnement précédent est correct il y a maintenant le problème de minorer u(n-1).

[aviateur]

En y réfléchissant un peu, il y a peut être un raisonnement plus simple:
pour n=2, n= 3 on sait qu'il y a toujours possibilités d'écrire un bon mot.
Supposons qu'il existe n tel que pour j=2,....,n on puisse toujours écrire un bon mot mais pour n+1 il n'y a aucun bon mot.
En regardant cela de près on peut peut être aboutir qu'il n'y a aucun mot de longueur n et on obtient alors une contradiction.

[Ben314]

Perso., j'ai obtenu le résultat (*) en procédant à peu prés comme tu l'a fait, c'est à dire en disant que des mots de longueur qui ne sont pas bon, mais tels que le sous mot formé de premières lettres soit bon, il y en a exactement .
Or un tel mot est forcément constitué d'un bon mot de lettres suivi de l'unique (éventuelle) séquence de lettres interdite (mais il n'y a pas équivalence vu que si on forme un tel mot, on n'est pas certain que les premières lettres forment un bon mot).
On a donc la majoration c'est à dire [et ]
Et avec (que) ça, on peut effectivement montrer que pour tout .

(*) Et en allant regarder la soluce, c'est effectivement plus ou moins comme ça qu'ils font.

[aviateur]

Ok. Visiblement on voit mal une solution différente facile qui dénombrerait le nombre de bon mots vu les situations différentes.
Je me demande où ils sont allés cherché cet exo.

Une autre question maintenant. Si par exemple je prends n, ni trop grand, ni trop petit. n=10 , 20 ( à voir).
Et pour ce n là, je fourni une liste de mots interdits .
Trouver un bon mot ne serait-ce pas une énigme?
Ou alors, pour n plus grand, donner un algo qui construit un bon mot.

[nodgim]

A mon humble avis, cette question là est bien plus accessible que la première !

[aviateur]

Tu crois? j'aurais pensé le contraire

[aviateur]

Voici une liste de mots interdits de 2 à 20. Trouver un bon mot...
{{A,C},{C,B,C},{A,C,C,A},{A,C,C,B,B},{B,A,A,C,C,A},{C,B,A,C,B,A,C},{A,A,C,C,B,C,B,C},{A,C,C,A,A,B,C,B,C},{B,A,C,C,C,B,B,C,B,C},{C,B,B,A,B,C,A,B,C,B,A},{C,B,A,A,A,B,B,C,A,C,B,A},{B,A,A,B,A,C,B,A,C,A,A,C,C},{A,C,A,C,C,A,C,A,B,B,B,B,C,B},{B,A,A,B,B,C,C,A,A,A,A,A,C,C,B},{B,B,A,C,C,B,C,A,B,C,A,B,A,B,A,B},{A,B,A,A,A,A,C,C,C,B,B,C,B,A,A,C,A},{C,A,B,B,B,B,C,B,C,A,B,A,B,A,C,B,A,B},{A,C,B,B,B,B,A,C,A,A,A,A,C,A,C,C,B,B,B},{A,B,A,A,C,B,C,B,B,B,C,B,C,C,C,A,C,A,C,C}}

[aviateur]

rebonjour@nogdim.
Il y a deux énigmes ds mes remarques. Là première trouver un bon mot à partir d'un exemple comme ci-dessus, je ne sais pas si c'est plus facile que l'énigme de départ mais tu as peut être raison.
Par contre, trouver un algo qui construit pour un n quelconque à mon avis c'est plus difficile.
En effet ton algo (s'il est justifié) en donnant une solution construite explicitement démontre l'existence d'un bon mot. Il fait mieux, il répond à l'énigme de départ.
Bien sûr si tu fais une construction en essayant un mot à la fois ça ne démontre rien et l'algo serait trop lent.

[Ben314]

Je me demande où ils sont allés cherché cet exo.

Dans l'avant propos du bouquin, il est dit que :
Les exercices de ce livres ont été créés lors de diverses compétitions ayant eu lieu en Suède, aux USA, en Angleterre, dans l'ex-URSS, etc.
Mais il n'y a pas de référence exercice par exercice.

Sinon, concernant un Algo. pour trouver un bon mot, le premier qui me vient à l'esprit correspond à la preuve du bidule, à savoir de rajouter une à une des lettres à la fin en vérifiant à chaque fois que tout les sous-mots "finaux" ne sont pas interdit.
Et quand on tombe sur un truc interdit, on "revient en arrière" (donc un algo. profondément récursif).