Petit problème de combinatoire

[RomVi]

Bonjour à tous

Aujourd'hui une collègue m'a posé une colle : Son fils prépare un weekend d'intégration. Il va former 10 équipes qui s'affronteront en 1 contre 1 sur 5 jeux différents.
- Toutes les équipes doivent se rencontrer, il y aura donc 9 rencontres.
- Les 5 jeux sont joués en simultanés et il n'est pas possible de faire 2 rencontres au même moment sur le même jeu.
Le but est d'essayer de répartir au mieux, pour éviter qu'une équipe joue au même jeu trop souvent.

J'ai réussi a faire un planning ou chaque équipe rencontre les 9 autres, mais en ce qui concerne la répartition des jeux je pensais que chaque équipe jouerai à chaque jeu 1 ou 2 fois, mais je ne suis pas parvenu à cet objectif, au mieux, en tâtonnant, les équipes jouent chaque jeu 1, 2 ou 3 fois.
Est-ce seulement possible ?

Je suppose qu'il existe une méthode permettant de bien répartir les jeux, mais je ne l'ai pas trouvée...
-----

[invite51d17075]

Bjr

Aujourd'hui une collègue m'a posé une colle : Son fils prépare un weekend d'intégration. Il va former 10 équipes qui s'affronteront en 1 contre 1 sur 5 jeux différents.
- Toutes les équipes doivent se rencontrer, il y aura donc 9 rencontres.
- Les 5 jeux sont joués en simultanés et il n'est pas possible de faire 2 rencontres au même moment sur le même jeu.

je ne suis pas sûr de bien comprendre.
il y a donc 9 rencontres x 5 jeux donc 45 confrontations ?
quand il y a rencontre, c'est toute l'équipe X qui rencontre l'équipe Y ?
pourquoi devrait il y avoir plusieurs rencontres entre X et Y sur un même jeu ? ( si c'est le cas )

[RomVi]

En effet en me relisant je me rend compte que je me suis assez mal exprimé...

Il y a 9 rencontres pour chaque équipe (chaque équipe joue une fois contre tous les autres). En continu on a donc 5 x 2 équipes qui s'affrontent sur 5 jeux différents.
et au total 5 x 9 = 45 matchs seront disputés. Voici par exemple un planning possible pour ces rencontres (équipes numérotés de 1 à 10) :

1 - 10
2 - 9
3 - 8
4 - 7
5 - 6

1 - 9
10 - 8
2 - 7
3 - 6
4 - 5

1 - 8
9 - 7
10 - 6
2 - 5
3 - 4

1 - 7
8 - 6
9 - 5
10 - 4
2 - 3

1 - 6
7 - 5
8 - 4
9 - 3
10 - 2

1 - 5
6 - 4
7 - 3
8 - 2
9 - 10

1 - 4
5 - 3
6 - 2
7 - 10
8 - 9

1 - 3
4 - 2
5 - 10
6 - 9
7 - 8

1 - 2
3 - 10
4 - 9
5 - 8
6 - 7

La difficulté est de répartir au mieux les jeux pour que chaque équipe passe au moins 1 fois par chaque jeu, et pas trop souvent sur le même. Intuitivement je pense qu'il est possible de trouver une répartition permettant de jouer soit 1 fois soit 2 fois à chaque jeu, mais je ne sais pas comment le trouver autrement qu'en tâtonnant, et c'est peut être impossible.

[invite51d17075]

Il y a 9 rencontres pour chaque équipe (chaque équipe joue une fois contre tous les autres). En continu on a donc 5 x 2 équipes qui s'affrontent sur 5 jeux différents.
et au total 5 x 9 = 45 matchs seront disputés.

y'a un pb de nb de rencontres.
soit 1 jeu.
si toutes les équipes se rencontrent sur ce seul jeu, il y a déjà 45 matchs pour que toutes les confrontations aient lieu.
on peut prendre ton tableau en exemple.

[A voir en vidéo sur Futura]

[RomVi]

Non chaque équipe doit rencontrer toutes les autres et chaque équipe doit passer au moins une fois par chaque jeu, mais il n'est pas nécessaire que toutes les rencontres possibles passent par tous les jeux.

[invite51d17075]

OK, et que doit on optimiser ?

[RomVi]

mon but est de faire passer chaque équipe soit 1 soit 2 fois par jeu (pour éviter trop de répétitions). J'ai construis un tableau mais au mieux les équipes passent 1, 2 ou 3 fois par jeu.

[vgondr98]

tableauequipe.jpg
Je crois que c'est bon.

[RomVi]

Si j'ai bien compris le décompte en bas de colonne à droite le jeu bleu sera pratiqué 8 fois et le jaune 10 fois, donc ça ne fonctionne pas, vu qu'on a 9 rounds pendant lesquels les 5 jeux sont joués simultanément. Il faut forcément 9 parties jouées pour chaque jeu.

[vgondr98]

tableauequipe.jpg
Bonjour, j'ai changer la couleur en BD de jaune à bleu, ce qui fait un jeu bleu en plus pour B et un jeu bleu en plus pour D, ainsi qu'un jeu jaune en moins pour B et un jeu jaune en moins pour D.

[RomVi]

Visiblement ça marche cette fois, il ne reste plus qu'à trouver comment répartir toutes ces parties en 9 rounds contenant chaque fois 5 jeux différents.
Est-ce que tu utilises un algorithme, ou tu as essayé au hasard ?

[vgondr98]

J'ai commencé par la ligne A, où il n'y avait quasi aucune contrainte (à part qu'il fallait au maximum 2 jeux identiques pour les 9 rencontres).
J'ai décompté les couleurs pour les dix équipes.
Je suis passé à la ligne B, qui était déjà plus contrainte mais c'était simple car les équipes B,C,D,E,F,G,H,I et J n'étaient associés qu'a un seul jeu à ce moment-là.
J'ai décompté les couleurs pour les dix équipes.
Je suis passé à la ligne C, qui était encore plus contraint car certaines équipes avaient deux jeux associés de la même couleur.

Et ainsi de suite..

A un moment cela à coincé au niveau de la ligne G (il me semble) car je devais mettre la couleur verte entre l'équipe J et G or le J avait déjà deux couleurs vertes.
Cependant, j'ai pu intervertir les couleurs verte et rouge entre BG et BJ.

Après comme tu le sais, j'avais un excès de jeux jaunes et un déficit de jeux bleus que j'ai pu résoudre en changeant un jeu jaune par un jeu bleu.

Ce qui est marrant, c'est que pour que cela marche, il semblerait qu'il faille que le nombre total de partie (45) soit le produit du nombre de jeu (5) par le nombre de rencontres pour une équipe donnée (9).

[RomVi]

J'ai tenté de ranger les rencontres avec mon tirage plus haut et ça ne colle pas.
La difficulté est qu'il faut minimiser le nombres de répétition des jeux par équipes, mais il faut aussi que les jeux ne soient pas joués en double lors d'un même round.

[vgondr98]

tableauequipe.jpg
J'ai réussi a organiser 6 round mais après cela a coincé car j'avais une même équipe qui participait à 2 jeux lors d'un même round ce qui n'est pas possible.

[invite6486d7bd]

Une idée peut-être :

Session 1
A1F
B2G
C3H
D4I
E5J

On fait tourner le "cercle" ABCDEFGHIJ (dans le sens lévogyre ici, mais qu'importe)

Session 2 :
F1G
A2H
B3I
C4J
D5E

Etc.

Session 3 :
G1H
F2J
A3I
B4E
C5D

Session 4 :
H1J
G2I
F3E
A4D
B5C

Session 5 :
J1I
H2E
G3D
F4C
A5B

Session 6 :
I1E
J2D
H3C
G4B
F5A

Session 7 :
E1D
I2C
J3B
H4A
G5F

Session 8 :
D1C
E2B
I3A
J4F
H5G

Session 9 :
C1B
D2A
E3F
I4G
J5H

[invite6486d7bd]

Presque.
Il y en a qui jouent deux fois contre le même adversaire...

[vgondr98]

Je me suis trompe au 4ème où je fait jouer D 2 fois.

[vgondr98]

tableauequipe.jpg
Je ne sais pas ce que tu en penses, là j'ai un léger excès de jeu orange.
Il est peut-être possible de permuter les couleurs dans le dernier round HI DJ CG AE BF pour voir si cet excès disparaît.

[RomVi]

Ça me semble déjà bien optimisé.
Je pense qu'il doit exister une méthode pour logique organiser les jeux et les équipes, mais je ne l'ai pas trouvée.