Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
240 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

7 joueurs, 7 pays, 7 parties

Envoyé par jimi124 
7 joueurs, 7 pays, 7 parties
il y a cinq mois
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...)
Re: 7 joueurs, 7 pays, 7 parties
il y a cinq mois
avatar
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.
Re: 7 joueurs, 7 pays, 7 parties
il y a cinq mois
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.
Re: 7 joueurs, 7 pays, 7 parties
il y a cinq mois
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é...
Re: 7 joueurs, 7 pays, 7 parties
il y a cinq mois
avatar
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.
Re: 7 joueurs, 7 pays, 7 parties
il y a cinq mois
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 ?
Re: 7 joueurs, 7 pays, 7 parties
il y a cinq mois
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. sad smiley

Citation

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
Re: 7 joueurs, 7 pays, 7 parties
il y a cinq mois
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.
Re: 7 joueurs, 7 pays, 7 parties
il y a cinq mois
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
Re: 7 joueurs, 7 pays, 7 parties
il y a cinq mois
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.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 148 605, Messages: 1 497 701, Utilisateurs: 28 280.
Notre dernier utilisateur inscrit Section Paloise.


Ce forum
Discussions: 886, Messages: 7 497.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page