Organiser un tournoi

[Mathusalem]

Bonjour,

Je dois aider a l'organisation d'un tournoi de physique qui aura lieu en mars 2014. La structure est la suivante : N equipes s'affrontent. Elles sont divisees en P poules et s'affrontent J jours. Chaque jour, les affrontements se font dans une poule. Le jour suivant, les poules sont refaites. A la fin des J jours les 3 meilleures equipes sont selectionnees pour la finale.

En pratique, ce sont 12 equipes en 4 poules de 3, pendant 6 jours, ou 16 equipes en 4 poules de 4.

Une critique qui fut emise l'annee precedente etait que les equipes se confrontaient trop souvent, et meme, que certaines equipes ne se recontraient pas du tout durant le tournoi.

J'avais en tete de resoudre ce probleme en force brute avec matlab, mais je fais appel a vous avant pour savoir si ca vaut la peine de coder le probleme suivant :

- Etant donnees N equipes reparties (le plus equitablement possible) en P poules, s'affrontant a l'interne d'une poule 1 fois par jour, pendant J jours, existe-t-il une repartition des equipes telle que chaque equipe affronte toutes les autres, ou que les equipes ne voient qu'une fois chaque equipe ?

Le plus equitablement possible veut dire que pour 10 equipes et 3 poules, on ferait 4,3,3. Si cette question est trop compliquee, on peut se concentrer sur le cas de 12 equipes et 4 poules de 3. Quels outils sont a utiliser pour caracteriser l'existence de la configuration qui m'interesse ? Une sorte de theorie des graphes?

[nuage]

Salut,
pourquoi ne pas essayer quelque chose du genre système suisse :
on fait s'affronter les équipes ayant le même niveau de résultat à chaque étape de la compétition.
Voici un lien sur les règles d’appariements aux échecs voir p 124 du pdf

[Mathusalem]

Merci de l'input Nuage. Malheureusement, la structure du tournoi est non-négociable, car elle nous est imposée. Ce qui n'est pas fixé, c'est comment les équipes sont distribuées à l'intérieur des poules de jour en jour.

J'ai déjà codé quelques algorithmes, mais la force brute est totalement inefficace.

Supposons qu'il y a 10 équipes. C(10,2) = 45 sont tous les couples que je peux former à partir de ces 10 équipes, où un couple est formé par le fait que les équipes se 'voient'.

Si j'ai des poules de 4, 3 et 3, il y aura chaque journée C(4,2) + C(3,2) + C(3,2) = 12 couples formés.

Si le tournoi se déroule sur 6 journées, il va se former 72 couples, mais il y en au maximum 45 qui sont distincts. Ce que je veux réussir à faire, c'est qu'il n'y ait aucun des 45 couples représenté 0 fois, et ensuite minimiser le nombre de fois que les couples se voient. Autrement dit, pour 6 journées, des poules de 4,3 et 3, je veux réussir à faire

72 = 18*1 + 27*2

C'est-à-dire que sur les 45 couples distincts, 18 apparaissent une seule fois, et 27 seulement 2 fois. Je n'arrive pas à déterminer analytiquement si c'est possible. Donc j'essaye de coder un algorithme intelligent qui essaye de trouver la solution minimale au sens ci-dessus.

Ceci me garantirait que chaque équipe voie toutes les autres, mais au maximum 2 fois.