7 joueurs, 7 pays, 7 parties

jimi124
jimi124
dans Combinatoire et Graphes
Dans le jeu Diplomatie on a 7 pays, et 7 joueurs s'affrontent. Pour équilibrer l'influence du pays tiré au sort, certains tournois sont en 7x7x7 : il y a 7 parties où les 7 joueurs jouent les 7 pays différents. On peut facilement faire des répartitions, par exemple une répartition circulaire, mais un problème survient quand aux voisins respectifs.
Deux questions se sont posées entre nous, une purement mathématique où je bloque, une plus liée au jeu où on peut avoir des solutions à la main un peu fastidieuses, mais sans méthode théorique.

1. Combien y a-t-il de répartitions possibles vérifiant le fait que chaque joueur doit jouer sur chaque partie et sur chaque pays ?

2. Suivant les pays, on a 3, 4 ou 5 voisins. Existe-t-il une répartition où chaque joueur se retrouve voisin de chaque joueur entre 3 et 4 fois (par exemple) ?

3. (pour le plaisir) : peut-on généraliser les deux problèmes à n quelconques joueurs, pays, parties ? et nij voisins quelconques entre les pays i et j ? et pour ces nij voisins, mettre un "coefficient de proximité" cij entre 0 et 1 ? ;)


Quelques précisions / remarques :

Pour la question 2, les pays (avec leurs voisins, du plus proche au plus éloigné) :
- Allemagne (France, Angleterre, Russie, Italie, Autriche)
- Angleterre (Allemagne, France, Russie)
- Autriche (Italie, Russie, Turquie, Allemagne)
- France (Allemagne, Angleterre, Italie)
- Italie (Autriche, France, Turquie)
- Russie (Turquie, Autriche, Angleterre, Allemagne, Italie)
- Turquie (Russie, Autriche, Italie)

Pour la question 1, il me semble que cela revient, si on avait n=8, à positionner 64 jetons, 8 de 8 couleurs différentes, sur les 64 cases d'un échiquier et on veut le nb de possibilités que chaque ligne et chaque colonne contienne les 8 couleurs ? Ou la probabilité que cela arrive, modulo un facteur 64! ? J'ai pas trop trouvé de réponses à cette question !

Pour la question 1, avec n=1 ou 2, on n'a qu'une seule répartition possible (le numéro de la partie n'a pas d'importance).
Avec n=3, supposons 3 pays A, B et C et 3 joueurs 1, 2 et 3. Les répartitions possibles sont les suivantes :
A1 B2 C3
A2 B3 C1
A3 B1 C2, que l'on peut noter ainsi :
123
231
312

et :
132
213
321

Donc avec n=3, 2 possibilités. Avec n=4, je trouve à la main 18 possibilités. Avec n=5, je dénombre, sauf erreur, 1056 possibilités.
Avec n=6 ou 7, ça explose ! Et je ne trouve pas de généralisation possible. Un programme informatique permettrait de trouver pour n=7, j'avoue que j'ai pas tenté ?

Voilà, merci bien d'avoir tout lu ! :)

PS : pour la question 1, il s'agit de faire en fait 6 dérangements successifs, si je m'exprime bien. On sait que le nombre de dérangements pour n=7 vaut 1854, mais dès le 2ème dérangement, je bloque (en effet, cela dépend du 1er à chaque fois...)

Réponses

  • lourrran
    lourrran
    Ma modeste contribution :
    Pour la 2ème question.
    L'Allemagne a 5 voisins, l'Angleterre a 3 voisins, etc, la somme donne 26 couples (Pays1, Pays2).
    En fait 13 couples, parce que chaque couple est compté 2 fois.

    Au bout de 7 parties, on a donc 'asssocié' 7x13=91.

    Et en termes de couples de joueurs, on a 7x6/2=21 couples de joueurs.
    91/21= 4.333
    Donc, si on se débrouille bien, chaque joueur aura été voisin de chaque autre joueur entre 4 et 5 fois, et non pas entre 3 et 4 fois. Le joueur A sera voisin de B C D et E 4 fois chacun, et voisin de F et G 5 fois chacun.

    La question 1 est effectivement très difficile.
    Et comme toi, je pense que seul un recensement systématique par programme permettra de répondre à la question.

    En fait, on peut penser au jeu de Sudoku. 9 lignes = 9 parties, 9 colonnes = 9 pays ; chaque numéro (= chaque joueur) apparaît une fois et une seule dans chaque ligne et chaque colonne.
    Au Sudoku, on a une contrainte de plus : les Carrés 3x3 ...
    Malgré cette contrainte supplémentaire, le nombre de grilles valides au jeu de Sudoku est 6 670 903 752 021 072 936 960 !!!!

    Cf Wikipedia

    Il faudrait enlever les symétries (si je permute la ligne 1 et la ligne 2, tu considères que c'est la même grille)
    Donc diviser par 9!.

    C'est quand même énorme, et ça laisse présager que même pour 7, on aura un nombre énorme.
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • PetitLutinMalicieux
    PetitLutinMalicieux
    Bonjour

    L'Allemagne a l'Italie pour voisin mais l'Italie n'a pas l'Allemagne pour voisin. De même, Angleterre France. Juste un oubli ?

    Lourran a raison. Ta situation est proche du sudoku. Donc difficile d'apporter une solution totale.

    A mon avis, le plus simple est de coder tes contraintes et de faire tous les cas possibles. Ajoute des contraintes jusqu'à avoir un nombre raisonnable de possibilités (quelques millions).

    Exemples de tournois :
    1234567 2143675 3412756 4567123 5376214 6725341 7651432
    Ou
    1234567 2143675 3761452 7615243 6572134 4356721 5427316
    Ou
    1234567 2143675 5367124 7652431 4716352 6475213 3521746

    Chaque ligne est un tournoi. Chaque mot est un tour. Chaque chiffre est le pays du joueur de rang égal à la place dans le mot.
    Exemple, sur le premier tournoi proposé, au tour 3, le joueur 6 a le pays 5.

    Bonne chance.
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
  • jimi124
    jimi124
    Merci pour ces retours, j'avais effectivement zappé le sudoku, je vais tenté de creuser cela.

    Et puis exact, des oublis ! Je rectifie :

    Pour la question 2, les pays (avec leurs voisins, du plus proche au plus éloigné) :
    - Allemagne (France, Angleterre, Russie, Italie*, Autriche*)
    - Angleterre (Allemagne, France, Russie)
    - Autriche (Italie, Russie, Turquie, Allemagne*)
    - France (Allemagne, Angleterre, Italie)
    - Italie (Autriche, France, Turquie, Russie, Allemagne*)
    - Russie (Turquie, Autriche, Angleterre, Allemagne, Italie)
    - Turquie (Russie, Autriche, Italie)

    J'ai mis une astérisque * pour les voisins lointains qui pourraient être les 5èmes voisins des joueurs qui en auraient déjà 4.


    La piste des dérangements est-elle utilisable, sinon ? Il n'y a pas tant de types de dérangements en fait, mais bon, pas facile...


    Sinon, un lien un peu éloigné...
  • lourrran
    lourrran
    Je ne pense pas que la piste des dérangements soit exploitable.
    Combien de dispositions pour le tour n°2 : ok , nombre de dérangements.
    Mais ça bloque là.
    Pour le tour n°3, on doit compter l'intersection entre les dérangements de tour n°1 et les dérangements de tour n°2 ... et là, on n'a plus de formule toute faite.
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • jimi124
    jimi124
    Sur cette page, en cochant "dérangements" et en entrant 7, on obtient le détail des 1854 permutations suivant le nb et la longueur des cycles. Il y a quelques cas possibles à traiter de manière équivalente.

    On peut sans perte de généralité commencer la 1ere ligne par 1234567, et commencer les lignes suivantes par 2, 3, 4, ... :
    1234567
    2xxxxxx
    3xxxxxx
    4xxxxxx
    5xxxxxx
    6xxxxxx
    7xxxxxx

    Il faut ensuite multiplier le nombre de possibilités par 6! pour prendre en compte toutes les 1eres lignes possibles.

    Et là, je me demande si on ne peut pas faire qqch par récurrence ?
  • PetitLutinMalicieux
    PetitLutinMalicieux
    Bravo jimi124. J'avais oublié cette simplification. Le joueur 1 a le pays de numéro égal au numéro du tour. Du coup, on peut faire la liste complète des tournois possibles. Il y en a 16942080. Environ 16 millions.

    Je posterais volontiers le fichier sur le forum, mais la version zippée fait 147 Mo. :-(
    1 1234567 2143675 3412756 4567123 5376214 6725341 7651432
    2 1234567 2143675 3412756 4567123 5376214 6725431 7651342
    3 1234567 2143675 3412756 4567123 5376214 6751342 7625431
    4 1234567 2143675 3412756 4567123 5376214 6751432 7625341
    5 1234567 2143675 3412756 4567123 5376241 6725314 7651432
    (...)
    16942076 1234567 2765431 3672154 4527613 5413276 6341725 7156342
    16942077 1234567 2765431 3672154 4527613 5413276 6351742 7146325
    16942078 1234567 2765431 3672154 4527613 5413726 6341275 7156342
    16942079 1234567 2765431 3672154 4527613 5416372 6143725 7351246
    16942080 1234567 2765431 3672154 4527613 5416372 6341725 7153246
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
  • PetitLutinMalicieux
    PetitLutinMalicieux
    En ce qui concerne la question 2, question du voisinage, comme tu as 3 pays avec 3 voisins, 1 pays avec 4 voisins, et 3 pays avec 5 voisins, la moyenne des voisins sera forcément 4. Mais on peut calculer un score qui évalue l'écart à la moyenne; pour savoir par exemple si le joueur 1 et le joueur 7 n'arrêtent pas de se voir dans un tournoi, alors que d'autres tournois sont plus équilibrés.

    Je considère que deux joueurs marquent 1 point quand leurs pays sont voisins. Pour l'instant, la relation est symétrique.
    J'obtiens une somme totale de 196, quelque soit le tournoi. Normal.

    Je somme à nouveau en considérant l'écart à la moyenne, que je mets au carré. 
    total += ( 4 - score_de_relation_entre_joueurs(i,j) )^2
    Le premier tournoi reçoit un score de 192. Alors que le second 184. Et le troisième 172. On a bien une différence.
    Puis, je minimise ce total.
    Le tournoi qui sortira ne sera pas unique, mais sera le premier avec le score le plus petit.

    Et le gagnant est ...
    1234567 2143675 3417256 4675132 5326741 6751423 7562314
    Autrement dit :
    1234567
    2143675
    3417256
    4675132
    5326741
    6751423
    7562314

    avec un score ainsi calculé de 140.
    Dans cette configuration, tous les joueurs ont les autres pour voisins 4 ou 5 fois. Jamais 2 fois, ni 7 fois.
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
  • jimi124
    jimi124
    Merci !

    Juste une précision, pour les pays 1,2,3..., ce sont bien les pays dans l'ordre (alphabétique) que j'avais mis ?
    ça semble très bien en effet !

    Je veux bien le gros fichier, voire le script, si ça te dérange pas ! (je t'envoie un mp)

    Merci encore
  • PetitLutinMalicieux
    PetitLutinMalicieux
    Oui, j'ai repris ta (seconde) liste et je l'ai transformé en nombres.

    Pour ceux qui se demandent le tournoi le moins équilibré est :
    1234567 2465713 3651274 4517326 5723641 6172435 7346152
    avec un score de 308.

    Aucun tournoi permet à 2 personnes de s'éviter.
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 17

GonLirone93i.zitoussim.c1zeste +12 Invités