Enigme Abc 1/2 @ Prise2Tete

Ebichu · #1

Bonjour à tous.

Je vous propose une question issue d'un problème ouvert dont j'ai eu l'idée suite au problème de scarta (même si le lien n'est pas flagrant). Je n'ai pas eu encore le temps de beaucoup creuser.

On fabrique un dictionnaire de la manière suivante. Le mot "a" appartient au dictionnaire, et si un mot appartient au dictionnaire, c'est également le cas d'un mot obtenu :
- en remplaçant un "a" par "bc".
- en remplaçant un "b" par "ca".
- en remplaçant un "c" par "ab".

Par exemple, partant de "a", on en déduit que "bc" appartient au dictionnaire, puis "cac" (ou bien "bab" : il n'y a que deux mots de longueur 3 dans le dictionnaire), puis "cbcc", puis "cbabc"...

Combien y a-t-il de mots de longueur 8 dans le dictionnaire ?

Attention à la loi forte des petits nombres... https://www.maa.org/sites/default/files … 97-712.pdf

enigmatus · #2

Bonjour Ebichu,
Je ne l'ai pas fait à la main, mais je trouve 390 mots de longueur 8, et 583 mots de longueur ≤ 8.
Voici quelques autres valeurs :

Code:

lon=  1 nb=     1 tot=     1
lon=  2 nb=     1 tot=     2
lon=  3 nb=     2 tot=     4
lon=  4 nb=     5 tot=     9
lon=  5 nb=    14 tot=    23
lon=  6 nb=    42 tot=    65
lon=  7 nb=   128 tot=   193
lon=  8 nb=   390 tot=   583
lon=  9 nb=  1185 tot=  1768
lon= 10 nb=  3586 tot=  5354
lon= 11 nb= 10862 tot= 16216
lon= 12 nb= 32929 tot= 49145

Édité : Voici quelques valeurs en plus

Code:

lon= 13 nb=   99883 tot=   149028
lon= 14 nb=  303000 tot=   452028
lon= 15 nb=  919080 tot=  1371108
lon= 16 nb= 2787558 tot=  4158666
lon= 17 nb= 8453921 tot= 12612587

Ebichu · #3

Bonne réponse, bravo Je trouve les mes nombres que toi.

nodgim · #4

Je dirais comme ça qu'il y aurait (3^(n-2) +1) / 2 nombres de n chiffres, mais sans aucune certitude, faute d'être allé au bout....

Ebichu · #5

@nodgim : non, les résultats divergent légèrement de ta formule à partir de n=6.

J'ai employé la même méthode qu'enigmatus, si tu vois ce que je veux dire. Ça ne veut pas pour autant dire qu'il n'y a pas une autre façon de faire, mais ça me parait compliqué.

Franky1103 · #6

Pour une longueur N, je trouve: 3.(N-1)! mots; pour une longueur 8, donc 15 120 mots, mais ce n'est pas validé , probablement à cause de possibles doublons.
Quant à loi forte des petits nombres, je n'y comprends pas grand chose re-.

Ebichu · #7

@Franky1103 : effectivement, il doit y avoir des doublons car la bonne réponse est nettement inférieure. Quant à la loi forte des petits nombres, elle dit en substance que ce n'est pas parce qu'une suite commence par 1,2,3,4,5 que le terme suivant sera 6, il faut se méfier des motifs que l'on voit parfois émerger.

enigmatus · #8

J'ai rajouté quelques valeurs en #2.

gwen27 · #9

Bonjour,
J'en trouve 390 de aaabaaac à cccbcccc

Ebichu · #10

@enigmatus : merci !

@gwen27 : oui, bravo ! Je trouve les deux mêmes mots.

Ebichu · #11

Merci aux participants. Félicitations à ceux qui ont trouvé : la méthode la plus évidente était de fabriquer un programme pour calculer la valeur recherchée. Il est, comme souvent, surprenant qu'une définition aussi simple engendre tant de complications.

nodgim · #12

J'ai cherché, en marge de la question, à savoir reconnaitre un mot du dictionnaire. Un mot donné appartient il oui ou non au dictionnaire ? Je n'ai pas trouvé. J'avais espoir de découvrir un invariant quelque part, mais pour l'instant rien. Pis, même en remontant l'algorithme, on n'est pas sûr de remonter à tout coup à la lettre origine (si on part du principe qu'il y a les 3 lettres de départ dans le dico). Par tâtonnement, on s'en sort bien sûr, mais pour l'instant, je n'ai pas trouvé de règle générale, à part que le mot doit contenir au moins 1 paire de lettre ab, bc ou ca, évidemment.

C'est un sacré casse-tête mathématique, ce truc, mine de rien....

Ebichu · #13

Ha, ravi de voir que tu t'es penché sur la question. J'ai commencé à creuser, mais je n'ai pas encore tout essayé.

Pour l'instant, j'ai remarqué que la parité du nombre de "a" de tous les mots de taille n est la même que celle de n, et celle de"b" et de "c" est différente de celle de n. Par exemple, les mots de taille 6 ont 0, 2 ou 4 "a", et 1, 3 ou 5 "b", ainsi que 1, 3 ou 5 "c".

Par ailleurs, si un mot appartient au dictionnaire, c'est le cas de son "antisymétrique" obtenu en le renversant et en inversant les "b" et "c" : par exemple, "acaaab" appartient au dictionnaire, donc "caaaba" aussi. À noter que certains mots sont leur propre antisymétrique, comme caab.

J'ai tendance à représenter le dictionnaire sur un arbre, dont la racine est "a", et dont un étage contient tous les mots de taille n. On relie par une arête un mot de taille n à tous les mots de taille n+1 obtenus en transformant une seule de ses lettres, par exemple, les fils du mot cac sont abac, cbcc et caab.

On remarque facilement que si un mot a deux fils, alors ces deux fils ont eux-mêmes un fils commun. En ce moment, j'essaie de mettre à jour de telles propriétés, plus précises, pour affiner un encadrement du nombre de mots de taille n.

Par exemple, j'ai trouvé un mot qui a deux parents, mais ces deux parents ne sont pas des frères. Ça fait un bon exercice pour ceux qui ont le courage

Ebichu · #14

Je continue à progresser. J'ai trouvé des invariants qui permettent de scinder l'ensemble des mots formés de a, de b et de c en 8 sous-ensembles disjoints, qui contiennent respectivement :

* a
* b
* c
* aa
* cb
* ba
* ac
* cba

Les invariants permettent de prouver que ces sous-ensembles sont disjoints. De plus, mes calculs informatiques semblent indiquer que ces sous-ensembles coïncident avec les familles issues des éléments donnés ci-dessus... mais qu'est-ce que j'appelle famille ?

La famille issue de "a" est constituée non seulement de a, de ses descendants bc, bab, cac, caab, cbcab... mais aussi des autres ancêtres de ses descendants, des descendants de ces ancêtres, et ainsi de suite. Par exemple, cbbb est un parent de cbcab, donc il appartient à la famille de "a", bien qu'il ne fasse pas partie de ses descendants.

Bref, j'arrive à dénombrer ces 8 sous-ensembles, par exemple, celui qui contient "a" comporte [latex]\dfrac{3^n-1}{8}[/latex] éléments si n est pair, et [latex]\dfrac{3^n+1+4.(-3)^\frac{n-1}{2}}{8}[/latex] éléments si n est impair, ce qui fournit un majorant du nombre d'éléments du dictionnaire. Ce majorant est à peu près égal au double des nombres calculés par enigmatus. Il reste à faire le tri, parmi la famille de "a", entre les éléments qui sont des descendants de "a" et ceux qui ne le sont pas.

nodgim · #15

Quel est le plus long mot du dico d'Ebichu qu'on peut trouver dans cette suite de 40 lettres ?

bacbcbbcbacaccccccbbcbbabbccaacbaccabbcc

Suite fournie par la fonction " ALEA() " d'un tableur.

ça se fait à la main, moyennant une bonne méthode.

Ebichu · #16

Je vais regarder ton problème, ça ne me semble pas simple a priori.

J'étais occupé à démontrer ce que, dans mon message précédent, je citais comme "mes calculs informatiques semblent indiquer que ces sous-ensembles coïncident avec les familles issues des éléments donnés ci-dessus".

J'ai réussi, je sais donc maintenant qu'il y a exactement 8 familles disjointes de mots ; j'ai en fait démontré que si on prend deux mots d'un même sous-ensemble, ces deux mots ont un descendant en commun.

Je vais bientôt avoir de quoi écrire un article sur le sujet

nodgim · #17

Je suis impatient de voir ça....

Un autre truc marrant, c'est qu'on peut fabriquer un mot du dico avec autant de lettres qu'on veut sans la moindre analyse ni référence aux nombres plus petits.

Ebichu · #18

Je ne comprends pas ce que signifie "sans la moindre analyse ni référence aux nombres plus petits" ?

Sinon, concernant ton problème, je sèche. On est tenté de faire de l'analyse rétrograde en identifiant les occurrences de "ab", "bc" ou "ca", puis en en choisissant une et en la remplaçant par "c", "a", ou "b", et ensuite en continuant avec une autre occurrence... Mais on ne sait pas quand on sera bloqué, ça ressemble beaucoup au solitaire. Tu as une méthode plus efficace pour le résoudre que de tester toutes les possibilités ?

nodgim · #19

Non, je n'ai pas de recette pour éviter de tester les différents cas. Il s'agit juste de les ordonner de la façon la plus efficace possible, aussi je ne garantis pas d'avoir la meilleure méthode. J'attends encore un peu avant de la présenter.

Sinon, encore une singularité sur les mots de ce dico (il ne payait pas de mine comme ça au début, cet algorithme, mais il est plein de ressources...) : En partant de 2 nombres du dico longs de x et y lettres, on peut les concaténer, moyennant une adaptation simple, pour en faire un autre mot du dico long de x+y lettres.

nodgim · #20

" Je ne comprends pas ce que signifie "sans la moindre analyse ni référence aux nombres plus petits" ? "

De quelle façon t'y prends tu pour construire un mot quelconque du dico de 10 lettres par exemple ?

Ebichu · #21

Ben, on remarque qu'en développant à partir de "a" systématiquement la lettre de droite, on obtient :
a
bc
bab
baca
bacbc
bacbab
bacbaca...
c'est-à-dire n fois "bac" suivi de "a", ou "bc", ou "bab". Ainsi on a un mot du dico de la taille que l'on veut.

Pour la concaténation, on sait que le premier mot comme le deuxième se ramènent à "a". Si on décale toutes les lettres du premier d'un rang, et toutes les lettres du deuxième de deux rangs, ils se ramènent respectivement à "b" et à "c", donc la concaténation de ces deux nouveaux mots se ramène à "bc", donc à "a". C'est donc un mot du dico. Etait-ce ton idée ?

nodgim · #22

C'est OK pour la concaténation.

Pour construire ton mot de 10 lettres, tu as pris une particularité de l'algorithme que tu as développée, ce qui limite tout de même le type de mots qui en résultent.
La construction à laquelle je pense est beaucoup plus générale, elle permet de construire un mot totalement au hasard dont on ne connait pas à priori les lettres du mot quui va en résulter.

En fait on construit un arbre avec une règle très simple et ensuite il ne reste plus qu'à décorer l'arbre par une guirlande de lettres qui feront apparaitre le mot. Magique non ?

Ebichu · #23

Mmh, cette histoire de concaténation est intéressante.

On démontre assez facilement que tout mot du dico issu de a s'exprime comme concaténation de deux mots plus petits. Jusqu'aux mots de 6 lettres, il y a une unique façon de procéder, ce qui permet de justifier l'égalité entre le nombre de mots de n lettres et les nombres de Catalan. En effet, un mot correspond à un parenthésage : par exemple, (a+(a+a))+a = (a+bc)+a = bab + a = cbcc.

À partir des mots de 7 lettres, il y a divergence : le nombre de Catalan vaut 132, mais la suite ne vaut que 128, ce qui traduit qu'il doit y avoir des mots de 7 lettres qui s'expriment de plusieurs façons comme la concaténation de mots plus petits. Lesquels ? Je n'ai pas encore eu le temps de le déterminer (un petit programme devrait faire ça très bien).

Ainsi, on obtient une majoration du n-ième terme de la suite par les nombres de Catalan qui est efficace pour les petites valeurs de n, mais nettement moins ensuite (asymptotiquement, moins que le majorant de l'ordre de 3^n/8 que j'ai donné plus haut).

nodgim · #24

C'est tout à fait exact, tu as fait la même analyse, et je commence à m'interesser à ces doublons, surtout avec la vision "arborifère" de ces mots ( j'en donnerai la description demain). Mais je doute qu'on tire une règle de ces doublons, je ne le sens pas bien....

Demain je tâcherais de donner aussi la solution de la recherche du plus long mot dans une suite.

nodgim · #25

L'arbre

Pour fabriquer un mot du dico de n lettres, on fabrique un arbre avec n-1 " V ". Un 1er V en bas et pour les suivants on pose leur pointe sur l'une des branches libres. Toutes les combinaisons sont autorisées, ainsi on peut concevoir un arbre élancé mais étroit si chaque V est posé sur l'une des branches les plus hautes, ou au contraire un arbre étalé mais bas où chaque V est posé sur l'une des branches les plus basses.

Une fois le dessin fait, il faut donner une lettre a, b ou c à chaque branche. On établit pour cela un chemin orienté qui démarre en bas à gauche de l'arbre et qui longe toutes les branches 2 fois, le 1er passage en montant par la gauche, le second en descendant par la droite. Quand le chemin est tracé, c'est comme si on avait enveloppé l'arbre d'une écorce.
Les lettres qu'on donnera aux différentes branches successives rencontrées le long du chemin sont : bcabcabc... et si on n'a pas fait d'erreur la dernière branche est obligatoirement "c".

Le mot se lit alors directement sur le chemin orienté: ce sont les seules n branches à extrémités libres successivement rencontrées.

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 05-05-2018 10:35:26

bAc

#0 Pub

#2 - 05-05-2018 18:10:55

avc

Code:

Code:

#3 - 05-05-2018 21:01:30

Ab

#4 - 06-05-2018 07:59:03

zbc

#5 - 06-05-2018 17:17:56

Acb

#6 - 06-05-2018 18:25:40

abx

#7 - 06-05-2018 20:06:41

Acb

#8 - 06-05-2018 21:27:44

anc

#9 - 07-05-2018 11:40:06

Acb

#10 - 07-05-2018 19:56:59

avc

#11 - 09-05-2018 15:15:19

avc

#12 - 09-05-2018 17:10:27

abv

#13 - 09-05-2018 19:12:14

anc

#14 - 16-05-2018 21:54:02

abv

#15 - 26-05-2018 16:51:11

Abbc

#16 - 28-05-2018 23:35:53

zbc

#17 - 29-05-2018 14:48:17

bAc

#18 - 30-05-2018 00:02:01

Ab

#19 - 30-05-2018 07:41:55

AAbc

#20 - 30-05-2018 08:36:49

Ab

#21 - 30-05-2018 11:28:43

abx

#22 - 30-05-2018 12:11:31

Abcc

#23 - 30-05-2018 19:23:50

anc

#24 - 30-05-2018 19:39:09

AAbc

#25 - 31-05-2018 07:46:12

Abbc

Réponse rapide

Sujets similaires

Pied de page des forums