Planning de matchs

Fulgrim

Bonjour
On m'a chargé de créer le planning des matchs d'une compétition dont le format est le suivant :

J'ai 4 groupes de 3 équipes, dont je note l'équipe 2 du groupe 3 par la variable $c_2$.
Chaque équipe affronte les 2 autres équipes de son groupe 2 fois en match aller-retour, et celles de 2 parmi les 3 autres groupes une seule fois. Par exemple $a_1$ joue 10 matchs : 4 contre $a_2$ et $a_3$, 3 contre $b_1$, $b_2$ et $b_3$ et 3 contre $d_1$, $d_2$ et $d_3$ (les groupes $A$ et $C$ ne se rencontrent pas, ainsi que les groupes $B$ et $D$).
Pour ceux qui connaissent, c'est presque le format NFL.

On m'a chargé de faire rentrer les 60 matchs en 10 semaines de 6 matchs (12 équipes donc 6 matchs chaque semaine) avec pour seules contraintes que les équipes ne jouent qu'un match par semaine et que les matchs aller-retour ne doivent pas se suivre. Ça paraît faisable, à première vue.

Sauf que je pense que c'est impossible, car si on met de côté les matchs entre groupes différents pour l'instant, il reste 4 matchs par équipe à jouer en 4 semaines. Or comme il n'y a que 3 équipes, chaque semaine il y aura une équipe qui restera sans match. Sans les matchs entre groupes différents, le problème est insoluble.

Ma question est donc : est-ce que avec les matchs entre groupes différents il est possible de régler ce problème ? Ou bien est-ce aussi insoluble ? Et comment le démontrer ?

lourrran

Si on met de côté les matchs qui permettent de combler les trous, on a des trous. Effectivement.
Mais si on ne met pas de côté les matchs entre groupes différents, on devrait pouvoir répondre au besoin.

Semaine 1 : (a2 , a3) , (b2 , b3) , (c2,c3) (d2,d3) ... et comblons les trous : (a1,b1), (c1,d1)
Semaine 2 : similaire, avec (a1,a3) , idem dans les autres poules. Et (a2,b2), (c2,d2)
Semaine 3 : similaire, avec (a1,a2) , idem dans les autres poules. Et (a3,b3), (c3,d3)

Semaine 4,5,6 : on fait les matches-retour dans chaque poule. et on comble les trous , mais avec A contre D au lieu de A contre B (a1,d1), (b1,c1) 

Et semaine 7 à 10, il nous reste les match entre équipes de poules différentes, et de numéros différents. A priori, on devrait pouvoir les planifier.
Semaine 7 : (a1,b2) (a2,b3),(a3,b1) (c1,d2) (c2,d3)(c3,d1)
En semaine7 , les équipes de la poule A rencontrent les équipes de la poule B, avec un numéro juste supérieur.
En semaine 8, les équipes de la poule A rencontrent les équipes de la poule B, avec un numéro juste inférieur.
En semaine 9 et 10, pareil, sauf que les équipes de la poule A rencontrent les équipes de la poule D.

On a une solution. Il suffisait juste d'avoir envie de trouver une solution.

LOU16

 Ce calendrier me semble convenir:

$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline 1&2&3&4&5&6&7&8&9&10 \\ \hline  a_1a_2&a_1a_3&a_2a_3&a_1b_1&a_1b_3 &a_1a_2&a_1a_3&a_2a_3&a_1d_1&a_1d_3\\  \hline a_3b_1&a_2b_3&a_1b_2&a_2b_2&a_2b_1&a_3d_1&a_2d_3&a_1d_2&a_2d_2&a_2d_1\\  \hline b_2b_3&b_1b_2&b_1b_3&a_3b_3&a_3b_2&d_2d_3&d_1d_2&d_1d_3&a_3d_3&a_3d_2\\ \hline  c_1c_2&c_1c_3&c_2c_3&c_1d_1&c_1d_3&c_1c_2&c_1c_3 & c_2c_3&c_1b_1&c_1b_3 \\  \hline c_3d_1&c_2d_3&c_1d_2&c_2d_2&c_2d_1&c_3b_1&c_2b_3&c_1b_2&c_2b_2&c_2b_1\\  \hline d_2d_3&d_1d_2&d_1d_3&c_3d_3&c_3d_2&b_2b_3&b_1b_2&b_1b_3&b_3c_3&b_2c_3 \\  \hline  \end{array}$$

Les matches -aller opposant les équipes d'un même groupe sont joués au cours des journées $1,2,3$ et les matches-retours au cours des journées $6,7,8.$

Fulgrim

Ah effectivement après m'être retrouvé bloqué je me suis convaincu que c'était impossible, à tort.
Merci à vous deux pour le coup de main !

Math Coss

Non, rien.