Evaluation nombre de parties jeu de dominos

Discussions générales concernant les mathématiques et n'entrant pas dans les catégories suivantes.
[participation réservée aux utilisateurs inscrits]
Règles du forum
Merci de soigner la rédaction de vos messages et de consulter ce sujet avant de poster. Pensez également à utiliser la fonction recherche du forum.
einstein301

Evaluation nombre de parties jeu de dominos

Message non lu par einstein301 »

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
rebouxo
Modérateur honoraire
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

Message non lu par rebouxo »

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
MC
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 399
Inscription : jeudi 24 avril 2008, 16:59

Re: Evaluation nombre de parties jeu de dominos

Message non lu par MC »

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 :

[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
K7.png (9.44 Kio) Consulté 2844 fois
dominosuite.gif
dominosuite.gif (3.71 Kio) Consulté 2844 fois
MC
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 399
Inscription : jeudi 24 avril 2008, 16:59

Re: Evaluation nombre de parties jeu de dominos

Message non lu par MC »

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.
Lucas.pdf
(48.83 Kio) Téléchargé 356 fois
einstein301

Re: Evaluation nombre de parties jeu de dominos

Message non lu par einstein301 »

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.
MC
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 399
Inscription : jeudi 24 avril 2008, 16:59

Re: Evaluation nombre de parties jeu de dominos

Message non lu par MC »

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
einstein301

Re: Evaluation nombre de parties jeu de dominos

Message non lu par einstein301 »

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
MC
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 399
Inscription : jeudi 24 avril 2008, 16:59

Re: Evaluation nombre de parties jeu de dominos

Message non lu par MC »

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
Répondre
  • Sujets similaires
    Réponses
    Vues
    Dernier message