Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

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

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 691

anc

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



Annonces sponsorisées :

 
Réponse :
  • |
  • Répondre

#0 Pub

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

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 493

abv

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

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

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 691

abx

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

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

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3437

Acb

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

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

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 691

avc

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

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

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2863
Lieu: Luxembourg

bAc

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

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

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 691

anc

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

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

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 493

bAc

J'ai rajouté quelques valeurs en #2.

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

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,780E+3

Ab

Bonjour,
J'en trouve 390 de aaabaaac à cccbcccc

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

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 691

Ac

@enigmatus : merci !

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

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

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 691

Abbc

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.

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

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3437

Abcc

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

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

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 691

bAc

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 smile

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

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 691

abx

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.

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Dans une course, vous doublez le 20ème, en quelle position êtes-vous ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete