Forum de mathématiques - Bibm@th.net

Aldarein

Membre

Inscription : 03-02-2023

Messages : 2

Création tournoi et problème combinatoire

Bonjour,

Je me suis mis en tête de créer un tournoi amical dans un sport qui se joue en 2v2. Comme il existe des écarts de niveaux et pour éviter que la création des équipes aient trop d'importances, je voudrais que chaque joueur joue une seule fois avec chaque autre joueur (comme partenaire) et deux fois en moyenne contre chaque joueur (comme adversaire donc). Au départ, je voulais créer ce tournoi pour 20 ou 24 joueurs, mais j'ai décidé de regarder ce qu'il se passe avec beaucoup moins de joueurs.
Pour 4 joueurs, il n'y a qu'une seule solution, c'est donc trivial. Chaque joueur a bien un partenaire différent durant les 3 tour et a chaque autre joueur comme adversaire 2 fois.
Pour 8 joueurs. Il faut donc 7 tours, et ça n'a déjà plus rien de trivial. J'ai néanmoins réussi à obtenir une solution (50% par tâtonnement et 50% par hasard) qui est la suivante:
Tour 1:
(1,2) contre (3,4)
(5,6) contre (7,8)

Tour 2:
(1,3) contre (6,7)
(2,8) contre (4,5)

Tour 3:
(1,4) contre (3,5)
(2,7) contre (6,8)

Tour 4:
(1,5) contre (2,6)
(3,7) contre (4,8)

Tour 5:
(1,6) contre (4,7)
(2,5) contre (3,8)

Tour 6:
(1,7) contre (5,8)
(2,4) contre (3,6)

Tour 7:
(1,8) contre (4,6)
(2,3) contre (5,7)

Dans cette configuration, chaque joueur joue bien une fois avec chaque autre. Cependant, chaque joueur joue contre chaque autre entre 1 et 3 fois. Ce n'est donc pas parfait mais je doute qu'on puisse obtenir exactement 2 donc je m'étais autorisé d'avoir un écart de 1 à ce niveau. Cet écart est cependant équitablement réparti, ce qui est important, je ne voudrais pas que le numéro de joueur ait d'impact sur la répartition des rencontres.

J'ai ensuite essayé de regarder avec 12 joueurs mais le tâtonnement et le hasard ne fonctionnent plus car il commence à y avoir vraiment beaucoup trop de combinaisons possibles.

Je me suis principalement concentré sur des alternatives à 8 et 12 joueurs pour essayer de comprendre et de trouver une méthode.

J'espère avoir été suffisamment clair dans mes explications.

Si quelqu'un pense avoir une solution ou une piste de réflexion, je suis preneur, merci d'avance.

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Création tournoi et problème combinatoire

Bonsoir,

Les joueurs d'échecs connaissent ce type de rencontres : on appelle ça tournoi toutes rondes. En plus aux échecs il y a une contrainte, il fait alterner le joueur qui commence (premier numéro cité) parce qu'il a les Blancs, ce qui constitue un petit avantage, petit mais réel.
Pour 6 joueurs :

Ronde 1 :  1-6   2-5   3-4
Ronde 2 :  6-4   5-3   1-2
Ronde 3 :  2-6   3-1   4-5
Ronde 4 :  6-5   1-4   2-3
Ronde 5 :  3-6   4-2   5-1

Chacun des joueurs rencontre 1 fois (et pas deux) chacun des n-1 autres.
Voilà les Tabelles d'appariements jusqu'à 24...

https://www.cjoint.com/c/MBduHJZMiq5

Je n'ai rien inventé, je me suis contenté de scanner un document officiel...
En cas de nombre impair, il y a un exempt différent à chaque tour.

@+

Aldarein

Membre

Inscription : 03-02-2023

Messages : 2

Re : Création tournoi et problème combinatoire

Bonsoir,

Les joueurs d'échecs connaissent ce type de rencontres : on appelle ça tournoi toutes rondes. En plus aux échecs il y a une contrainte, il fait alterner le joueur qui commence (premier numéro cité) parce qu'il a les Blancs, ce qui constitue un petit avantage, petit mais réel.
Pour 6 joueurs :

Ronde 1 :  1-6   2-5   3-4
Ronde 2 :  6-4   5-3   1-2
Ronde 3 :  2-6   3-1   4-5
Ronde 4 :  6-5   1-4   2-3
Ronde 5 :  3-6   4-2   5-1

Chacun des joueurs rencontre 1 fois (et pas deux) chacun des n-1 autres.
Voilà les Tabelles d'appariements jusqu'à 24...

https://www.cjoint.com/c/MBduHJZMiq5

Je n'ai rien inventé, je me suis contenté de scanner un document officiel...
En cas de nombre impair, il y a un exempt différent à chaque tour.

@+

Bonsoir,

J'étais effectivement tombé sur ce format, c'est de ça que je me suis inspiré pour essayer de créer une variante. Je me suis d'ailleurs servi des tablettes dont tu parles pour systématiser la création de mes paires de joueurs. Au passage, il existe plusieurs façon différentes d’apparier les joueurs et je n'ai pas réussi à déterminer si une méthode d'appariement était meilleures que les autres (mais j'ai fait confiance à celle utilisée par les joueurs d'échecs). Cependant, les échecs se jouent en 1v1 (il me semble). Hors dans mon cas, je cherche à créer des binômes de partenaires différents à chaque tour et de faire jouer les binômes deux à deux. C'est là que la complexité intervient. Il faut à la fois composer avec la contrainte des partenaires et des adversaires. Par exemple, si on essaye de construire ces rencontres de façon un peu "naïve", il arrive souvent qu'au 6 ou 7ème tour, le joueur 1 joue forcément avec le joueur 8 puisqu'il a déjà joué avec tout les autres. Sauf que le joueur 1 aimerait jouer contre le joueur 2 (qui doit jouer avec le joueur 3 car il a déjà joué avec tout les autres) et le joueur 8 aimerait jouer contre le jouer 7 (qui doit jouer avec le 6 car il a déjà joué avec tout les autres). On aboutit donc a une situation dans laquelle on tombe sur des conditions impossibles à satisfaire.
Bien sûr, on est alors tenté de modifier quelques matchs par-ci par-là pour harmoniser tout ça mais ça crée d'autres contradictions ailleurs. Et ce n'est que pour 8 et 12 joueurs... Au-delà, ça me semble miraculeux d'arriver jusqu'au dernier ou avant-dernier tour sans tomber sur des contraintes encore plus dures sur encore plus de joueurs.
J'espère avoir été assez clair.
Merci quand même d'avoir essayé d'apporter une solution.