Combinaison (jeu de société)

Nicolas MATHIEU · May 2017

Bonjour,

Je suis un auteur amateur de jeux de société et je butte sur un problème mathématique... aussi, je cherche humblement de l'aide...

J'explique :
Sur des tuiles (pièce en carton carrée de 4,5 cm de côté), j'ai des tuyaux.
Exactement 4 tuyaux sur chaque.
Chaque tuyau a une couleur : vert, bleu, rouge et jaune.
Il y a toujours les 4 couleurs sur chaque tuile.

Sur chaque côté de la tuile, il y a 2 entrées/sorties (soit 8 en tout pour chaque tuile).
Chaque tuyau rejoint une entrée et une sortie, unique dans les 2 cas, si bien que toutes les entrées sorties sont occupées.

Exemples :

Ma question : quelles sont toutes les combinaisons possibles ? (sachant que AB-CD-EF-GH est identique à CD-EF-GH-AB / EF-GH-AB-CD / GH- AB-CD-EF => 1er couple = vert, 2ème = bleu, 3ème rouge et 4ème jaune (par contre AB-EF-CD-GH est bien une combinaison possible))

merci pour votre aide,
merci

GaBuZoMeu · May 2017

Et BA-HG-FE-DC ? Autrement dit, peux-tu retourner ta tuile ?
Il importe de savoir si on compte les orbites pour l'action du groupe $C_4$ (cyclique d'ordre $4$) ou du groupe $D_4$ (diédral d'ordre 8).
622 (edit : erreur de calcul, voir correction ci-dessous) si on ne peut pas retourner, 330 si on peut, par la formule de Burnside (sauf erreur).

Nicolas MATHIEU · May 2017

Bonjour et merci pour ton intervention.

Non, la tuile n'est visible que d'un seul côté (donc pas de BA-HG-FE-DC).

Par exemple, les 4 tuiles suivantes sont en fait les mêmes (rotation 90°) :

GaBuZoMeu · May 2017

Dommage, ça ouvrirait plus de possibilités avec des tuiles transparentes que l'on peut retourner.
Je t'ai déjà donné une réponse : 622, mais j'ai fait une erreur de calcul bête. la bonne réponse est 636. Je peux te donner le détail du calcul par la formule de Burnside :
$$\frac14\left(\frac{8!}{(2!)^4}+ 4!\right)=636\;,$$
où le $4$ au dénominateur est le cardinal du groupe qui agit, le premier terme entre parenthèses est le nombre total de coloriages sans identification par les rotations et le deuxième terme le nombre de coloriages fixés par le demi-tour (les quarts de tour dans un sens ou dans l'autre ne fixant aucun coloriage). Je ne suis pas sûr que ça t'informe beaucoup plus.

Nicolas MATHIEU · May 2017

GaBuZoMeu
Merci... Je ne pensais pas qu'il y aurait autant de solutions, va falloir que je dégraisse...
Par contre, d'habitude, pour mes jeux, j'utilise le site internet DCODE mais il n'y a rien sur Burnside... Comment appliquer cette formule pour lister les 636 solutions ?

[Inutile de reproduire le message précédent. AD]

GaBuZoMeu · May 2017

Burnside dénombre et ne liste pas. Un moyen de lister est de lister les $8!=40320$ permutations de $A,B,\ldots,H$, d'attribuer pour chaque permutation la couleur rouge aux deux premiers, verte aux deux suivants etc. et d'éliminer les doublons. :-D
Tu peux avoir des tuiles qui sont des triangles équilatéraux avec seulement 3 couleurs. Ça pave toujours le plan, et il n'y a que 30 tuiles différentes.
Je demande 33% sur les recettes. ;-)

GaBuZoMeu · May 2017

Et si tu peux retourner tes triangles équilatéraux (ce qui à mon avis augmente l'intérêt du jeu), tu n'as plus que 18 tuiles différentes !!

Dom · May 2017

Bon, pavons avec des hexagones pour faire exploser les couleurs et les combinaisons ;-)

GaBuZoMeu · May 2017

D'accord Dom, tu vas pouvoir nous dire le nombre de tuiles hexagonales différentes, avec retournement possible pour limiter les dégâts. ;-)

Dom · May 2017

En suis-je seulement capable...
Je ne promets rien pour ce soir, mais je m'y essayerai.

Edit du soir, espoir :
Pour n=3, j'ai bien trouvé 30.
Pour n=4, je n'ai déjà pas trouvé 636, mais 630. (edit en gras souligné, coquille)
J'oublie certainement des tuiles et c'est "la tuile" 8-)

Je m'étais dit naïvement (sans voir toute la discussion) qu'il suffisait de coder une pièce par une anagramme de RRVVBBJJ (au nombre de ton premier terme) puis de diviser par 4 (rotations).

Je pensais en compter "trop"...

La nuit porte conseil...

GaBuZoMeu · May 2017

Dom, contemple par exemple RVBJRVBJ. Quand tu fais tourner, tu n'obtiens pas quatre anagrammes différents, mais deux !

Nicolas MATHIEU · May 2017

Bonjour,

Juste un lien vers le jeu pour info : http://www.facebook.com/crazyplumbers/

Pour des raisons de méca, je ne vais pas partir sur des triangles (et encore moins des hexagones). Ni sur du recto-verso car ça ouvrirait trop de possibilités aux joueurs et dans un jeu de société, trop de possibilités et de manipulations font perdre du temps (en général, les joueurs aiment bien jouer mais pas attendre).
De plus, il y a une configuration qui permet plus d'ouverture, ce sont toutes les "combinaisons" bouclant sur elles-mêmes (AB) (CD) (EF) et (GH), je les privilégierai dans mon choix.
Merci.

[Activation du lien. AD]

GaBuZoMeu · May 2017

En attendant que Dom ait calculé le nombre de tuiles hexagonales différentes, on peut se poser un autre problème de dénombrement : compter le nombre de tuiles carrées différentes, quand il n'y a plus de couleur (ou plus exactement, une seule couleur). On peut le faire dans le cas sans retournement, et dans le cas avec retournement.

Dom · May 2017

J'essaye de trouver quelques moments mais c'est le rush...

Évidemment je tente de trouver une méthode "à la main", sans tricher (je me souviens avoir démontré il y a quelques années cette formule des classes de Burside — est-ce bien celle-là ? —, mais ...c'est loin alors je préfère d'abord ne pas l'utiliser sans rien comprendre).

Si ce n'est pas fait dimanche soir, c'est que ma langue a été donnée au chat...

Dom · May 2017

Bon, je tente un réponse.

À dénombrer : les pièces hexagonales qui n'ont qu'une face visible (je reviendrai peut-être pour les tuiles transparentes), et telles que sur chacun des six côtés, on y voit deux couleurs ordonnées un couple de couleurs, choisies parmi 6, sous la contrainte d'avoir exactement deux fois chaque couleur, en tout, sur la même pièce.

J'obtiens : 1 245 000.

Tout cela après des calculs fastidieux et, je le crains, pouvant contenir des erreurs.
On comprend pourquoi cette formule de Burside existe.
J'ai utilisé une méthode presque exhaustive, mais même si je m'y prends mal, cela reste un exercice qui demande une certaine concentration.

Remarque : je n'ai pas compris l'exercice que tu proposes, avec "une seule couleur" et des carrés.

GaBuZoMeu · May 2017

sur chacun des six côtés, on y voit deux couleurs ordonnées,

Jusqu'à présent, on autorisait d'avoir les deux tuyaux sur un côté de même couleur. As-tu changé ?

Que dit Burnside ?

$$\frac16\left(\frac{12!}{2^6}+6!\right)=1\;247\;520\;.$$