Evaluation nombre de parties jeu de dominos
Evaluation nombre de parties jeu de dominos
Bonjour; je voudrais savoir combien il faudrait faire de parties de dominos pour retrouver la même configuration; je m'explique: une partie de dominos se joue à 3 ou 4 joueurs avec 28 dominos; à la fin de la partie,il y a bien une configuration de celle-ci; puis ensuite,les dominos sont retournés et mélangés et chaque joueurs reprend ses dominos pour éffectuer une nouvelle partie ,bien sûr il seront différents ;celle-ci une fois terminée,n'aura pas la même configuration que la précédente; au bout de combien de parties aura-t-on une configuration identique a la première,un nombre très élevé je présumes,mais alors,comment trouver ce nombre? il doit bien y avoir une solution. Merci BYE
-
- Modérateur honoraire
- Messages : 6962
- Inscription : mercredi 15 février 2006, 13:18
- Localisation : le havre
- Contact :
Re: Evaluation nombre de parties jeu de dominos
Il y a deux difficultés :
1. une de topographie : comment tu vas distinguer deux parties identiques à une symétrie où une rotation près, d'un domino.
2. Dans l'hypothèse que l'on arrive à faire la chose précédente, il y a vraiment beaucoup de possibilités à chaque coup.
Il y a une limite aux nombres de possibilités : $28 ! = 28 \times 27 \times \ldots \times 2 \times 1 $. Mais, le nombre de partie est certainement moins élevées.
Olivier
1. une de topographie : comment tu vas distinguer deux parties identiques à une symétrie où une rotation près, d'un domino.
2. Dans l'hypothèse que l'on arrive à faire la chose précédente, il y a vraiment beaucoup de possibilités à chaque coup.
Il y a une limite aux nombres de possibilités : $28 ! = 28 \times 27 \times \ldots \times 2 \times 1 $. Mais, le nombre de partie est certainement moins élevées.
Olivier
Re: Evaluation nombre de parties jeu de dominos
Bonjour,
Ce n'est pas clair de savoir ce qu'il faut compter exactement, comme l'a fait remarquer Rebouxo. Je propose la définition suivante : une configuration orientée du jeu de dominos est une suite $(D_1,D_2,\ldots,D_{28})$ comprenant les 28 dominos qui respecte la règle du jeu :
Il est naturel de dire que la configuration orientée $(D_1,D_2,\ldots,D_{28})$ et la configuration renversée $(D_{28},D_{27},\ldots,D_1)$ donnent la même configuration du jeu de dominos (on regarde les dominos de l'autre côté de la table).
Alors le nombre de configurations du jeu de dominos est $\displaystyle\frac{2\,729\,502\,720}{2}\times 4\times 3^6 = 3\,979\,614\,965\,760$, un peu moins de 4 billions.
Le nombre le plus mystérieux dans la formule ci-dessus est $2\,729\,502\,720$. C'est le nombre de circuits eulériens dans le graphe complet à 7 sommets. Voici le graphe complet à 7 sommets
Un circuit eulérien dans ce graphe (référence au problème des ponts de Koenigsberg traité par Euler) est un circuit qui emprunte chaque arête une fois et une seule (et qui revient forcément à son sommet de départ). A chaque arête du graphe complet est associé un domino (les deux numéros du domino sont les numéros des extrémités de l'arête). Les 21 arêtes correspondent aux 21 dominos qui ne sont pas des doubles, et les circuits eulériens correspondent donc exactement aux configurations orientées du jeu de domino privées des doubles.
Le double portant le numéro qui commence et finit a 4 positions possibles pour s'insérer dans le circuit (dont le début et la fin). Chacun des 6 autres doubles a 3 positions possibles. Ceci explique les facteurs $4$ et $3^6$ de la formule. La division par $2$ traduit l'oubli de l'orientation.
Le calcul du nombre de circuits eulériens est un problème difficile. J'ai trouvé le nombre $2\,729\,502\,720$ dans un article de B. McKay et R. Robinson paru il y a 10 ans.
Cordialement,
MC
Ce n'est pas clair de savoir ce qu'il faut compter exactement, comme l'a fait remarquer Rebouxo. Je propose la définition suivante : une configuration orientée du jeu de dominos est une suite $(D_1,D_2,\ldots,D_{28})$ comprenant les 28 dominos qui respecte la règle du jeu :
[attachment=1]dominosuite.gif[/attachment]
Il est naturel de dire que la configuration orientée $(D_1,D_2,\ldots,D_{28})$ et la configuration renversée $(D_{28},D_{27},\ldots,D_1)$ donnent la même configuration du jeu de dominos (on regarde les dominos de l'autre côté de la table).
Alors le nombre de configurations du jeu de dominos est $\displaystyle\frac{2\,729\,502\,720}{2}\times 4\times 3^6 = 3\,979\,614\,965\,760$, un peu moins de 4 billions.
Le nombre le plus mystérieux dans la formule ci-dessus est $2\,729\,502\,720$. C'est le nombre de circuits eulériens dans le graphe complet à 7 sommets. Voici le graphe complet à 7 sommets
[attachment=0]K7.png[/attachment]
Un circuit eulérien dans ce graphe (référence au problème des ponts de Koenigsberg traité par Euler) est un circuit qui emprunte chaque arête une fois et une seule (et qui revient forcément à son sommet de départ). A chaque arête du graphe complet est associé un domino (les deux numéros du domino sont les numéros des extrémités de l'arête). Les 21 arêtes correspondent aux 21 dominos qui ne sont pas des doubles, et les circuits eulériens correspondent donc exactement aux configurations orientées du jeu de domino privées des doubles.
Le double portant le numéro qui commence et finit a 4 positions possibles pour s'insérer dans le circuit (dont le début et la fin). Chacun des 6 autres doubles a 3 positions possibles. Ceci explique les facteurs $4$ et $3^6$ de la formule. La division par $2$ traduit l'oubli de l'orientation.
Le calcul du nombre de circuits eulériens est un problème difficile. J'ai trouvé le nombre $2\,729\,502\,720$ dans un article de B. McKay et R. Robinson paru il y a 10 ans.
Cordialement,
MC
- Pièces jointes
-
- K7.png (9.44 Kio) Consulté 2844 fois
-
- dominosuite.gif (3.71 Kio) Consulté 2844 fois
Re: Evaluation nombre de parties jeu de dominos
En suivant le fil de l'article de McKay et Robinson donné en lien dans l'article ci-dessus, je suis remonté au tome 4 des "Récréations mathématiques" d'Edouard Lucas. Je ne résiste pas au plaisir de vous communiquer une copie des pages 125-127 de cet ouvrage. Vous pourrez y voir que le nombre calculé par le Dr Reiss en 1859, au terme de 58 pages de calcul rébarbatif, est bien égal au double du nombre donné ci-dessus (Reiss comptait les configuration orientées). Vous pourrez aussi y voir le graphe complet.
Re: Evaluation nombre de parties jeu de dominos
Votre réponse me convient parfaitement mais je voudrais une précision, en plus du jeu de dominos classique, je possède un jeu à 55 dominos (double 9) un autre à 91 dominos (double 12) et un autre (en cours de fabrication) à 153 dominos (double 16), le nombre évalué pour 28 dominos est-il proportionnel pour les autres jeux que je viens de citer. Merci BYE.
Re: Evaluation nombre de parties jeu de dominos
Bonsoir,
L'article de McKay et Robinson contient toutes les données nécessaires sur le nombre de circuits eulériens des graphes complets pour apporter des réponses dans les cas que tu cites, en suivant la méthode que j'ai expliquée pour les dominos usuels.
Une première remarque : ce qui est compté ici est le nombre de configurations où tous les dominos du jeu sont posés, en respectant la règle. Or dans le cas des dominos avec nombres de 0 à 9, il est impossible de poser les 55 dominos en respectant la règle (il n'y a pas de circuit eulérien dans un graphe complet avec un nombre pair de sommets, ici 10).
Pour les 91 dominos avec nombres de 0 a 12, le nombre de configurations est à peu près $37,5\times 10^{60}$.
Pour les 153 dominos avec nombres de 0 à 16, c'est à peu près $5\times10^{121}$. Ca explose complètement.
Cordialement,
MC
L'article de McKay et Robinson contient toutes les données nécessaires sur le nombre de circuits eulériens des graphes complets pour apporter des réponses dans les cas que tu cites, en suivant la méthode que j'ai expliquée pour les dominos usuels.
Une première remarque : ce qui est compté ici est le nombre de configurations où tous les dominos du jeu sont posés, en respectant la règle. Or dans le cas des dominos avec nombres de 0 à 9, il est impossible de poser les 55 dominos en respectant la règle (il n'y a pas de circuit eulérien dans un graphe complet avec un nombre pair de sommets, ici 10).
Pour les 91 dominos avec nombres de 0 a 12, le nombre de configurations est à peu près $37,5\times 10^{60}$.
Pour les 153 dominos avec nombres de 0 à 16, c'est à peu près $5\times10^{121}$. Ca explose complètement.
Cordialement,
MC
Re: Evaluation nombre de parties jeu de dominos
Bonjour ; pourquoi le nombre donné par édouard lucas est le double du nombre que vous avez cité plus haut ; quelle est la bonne réponse à la question initiale ? Merci BYE
Re: Evaluation nombre de parties jeu de dominos
Je l'ai dit : le nombre calculé par Reiss et donné par Edouard Lucas est celui des configurations orientées. Le nombre qui figure dans mon messages est celui des configurations non orientées. Le premier est le double du second parce qu'une configuration non orientée peut être orientée de deux façons.
Cordialement,
MC
Cordialement,
MC
-
- Sujets similaires
- Réponses
- Vues
- Dernier message