Quelqu'un sur BGG a posé cette question… et le problème est loin d'être trivial. Pour les deux du fond que ça intéresse, je l'ai résolu de manière informatique. Je ne suis même pas sûr qu'il soit possible de le résoudre de manière purement analytique. Si quelqu'un se sent de le faire…
Je rappelle les règles : on place 10 tuiles (qui existent toutes en double, il y a donc en fait 5 groupes de 2 tuiles), de sorte que 2 tuiles identiques ne soient pas adjacentes (c'est cette règle qui rend l'analyse mathématique difficile).
Je pose le problème sous la forme d'un problème de satisfaction de contraintes. On a donc 10 variables v1 à v10 (correspondant aux 10 tuiles), pouvant prendre une valeur entre 1 et 10 (la position de la tuile sur le plateau, v3=5 signifie que la tuile n°3 doit être à la 5e place).
Chaque variable doit donc prendre une valeur différente. On pose la contrainte all_different(v1..v10).
v1 et v2 représentent des tuiles identiques, de même que v3 et v4, v5 et v6, etc. (v1=1, v2=3) et (v1=3, v2=1) représente donc la même solution. Pour éliminer ces solutions « parasites », on pose les contraintes v1 Deux tuiles identiques ne peuvent être adjacentes. Pour coder cette contrainte, il suffit de remplacer les contraintes précédentes par v1 Finalement, on peut remarquer que pour une solution donnée, on peut en obtenir une autre en inversant deux types de tuile. On peut donc simplifier les calculs en rajoutant la contrainte (v1 Voici le programme Prolog correspondant :
scand1sk dit:Quelqu'un sur BGG a posé cette question… et le problème est loin d'être trivial. Pour les deux du fond que ça intéresse, je l'ai résolu de manière informatique. Je ne suis même pas sûr qu'il soit possible de le résoudre de manière purement analytique. Si quelqu'un se sent de le faire… Je rappelle les règles : on place 10 tuiles (qui existent toutes en double, il y a donc en fait 5 groupes de 2 tuiles), de sorte que 2 tuiles identiques ne soient pas adjacentes (c'est cette règle qui rend l'analyse mathématique difficile). Je pose le problème sous la forme d'un problème de satisfaction de contraintes. On a donc 10 variables v1 à v10 (correspondant aux 10 tuiles), pouvant prendre une valeur entre 1 et 10 (la position de la tuile sur le plateau, v3=5 signifie que la tuile n°3 doit être à la 5e place). Chaque variable doit donc prendre une valeur différente. On pose la contrainte all_different(v1..v10). v1 et v2 représentent des tuiles identiques, de même que v3 et v4, v5 et v6, etc. (v1=1, v2=3) et (v1=3, v2=1) représente donc la même solution. Pour éliminer ces solutions « parasites », on pose les contraintes v1Deux tuiles identiques ne peuvent être adjacentes. Pour coder cette contrainte, il suffit de remplacer les contraintes précédentes par v1Finalement, on peut remarquer que pour une solution donnée, on peut en obtenir une autre en inversant deux types de tuile. On peut donc simplifier les calculs en rajoutant la contrainte (v1Voici le programme Prolog correspondant :
Et donc le résultat : 39 480 configurations de départ différentes.
Je dois faire partie des deux du fond... Même si la démonstration me passe un peu au dessus de la tête (mes cours de stats sont bien loin), la réponse est intéressante.
Intéressant - je ne m'étais jamais vraiment posé la question. Après un petit quart d'heure devant une feuille blanche, je ne vois pas de solution simple pour calculer ça. C'est assez facile de majorer par 10! / 2^5, mais pour aller plus loin...
loic dit:La solution dépend du nombre de joueurs, non ?
Ici, on parle de la situation de départ... avant la sélection des personnages... Parce que s'il faut pondérer les différents choix possibles, il faut ajouter un facteur selon le nombre de joueurs. Qui veut se lancer dans ce calcul (beaucoup plus simple)?
loic dit:La solution dépend du nombre de joueurs, non ?
Ici, on parle de la situation de départ... avant la sélection des personnages... Parce que s'il faut pondérer les différents choix possibles, il faut ajouter un facteur selon le nombre de joueurs. Qui veut se lancer dans ce calcul (beaucoup plus simple)?
Pour les personnages, c'est facile : comme au début, on ne peut choisir que des jeunes, chaque joueur prend deux personnages parmi neuf. Le premier joueur a le choix entre (9 2) = 36 combinaisons possibles, le deuxième 35, etc. Suivant si on considère l'ordre comme important ou non (il l'est pendant le choix, mais ne l'est plus une fois fait puisque l'ordre du tour dépend alors du choix), il y a 36!/(36-n)! ou (36 n) combinaisons possibles (respectivement 45 239 040 et 376 992)
