Tournoi
Bonjour,
Je ne savais pas trop où mettre ma question et aussi si je pouvais la poster sur ce forum mais je tente dans l'espoir d'une réponse.
Je souhaiterais organiser un tournoi mais j'ai un peu de mal au niveau de la répartition des équipes pour les activités.
Il y a 20 équipes et 10 activités différente.
Il faudrait que toutes les équipes passent sur chaque chaque activité sans jamais rerencontrer une équipe et donc jamais refaire la même activité.
J'ai eu beau faire plusieurs essais, je n'arrive qu'à réaliser 9 tours sur les 10 corrects.
Il doit y avoir un algorithme qui m'échappe ou c'est tout simplement impossible.
Est ce que vous pourriez m'aider à résoudre ce soucis s'il vous plaît.
Merci d'avance.
Je ne savais pas trop où mettre ma question et aussi si je pouvais la poster sur ce forum mais je tente dans l'espoir d'une réponse.
Je souhaiterais organiser un tournoi mais j'ai un peu de mal au niveau de la répartition des équipes pour les activités.
Il y a 20 équipes et 10 activités différente.
Il faudrait que toutes les équipes passent sur chaque chaque activité sans jamais rerencontrer une équipe et donc jamais refaire la même activité.
J'ai eu beau faire plusieurs essais, je n'arrive qu'à réaliser 9 tours sur les 10 corrects.
Il doit y avoir un algorithme qui m'échappe ou c'est tout simplement impossible.
Est ce que vous pourriez m'aider à résoudre ce soucis s'il vous plaît.
Merci d'avance.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Avec 20 équipes il y a 190 matchs différents possibles.
Chaque équipe doit rencontrer les 19 autres donc 19*20=380
Il y a 2 équipes par matchs donc 380/2=190
Comme il y a 2 équipes par match et activité, il faut au minimum 20*10/2 = 100 matchs pour que chaque équipe fasse chaque activité
Donc c'est possible
Voila
Merci de votre réponse.
Auriez vous une idée de comment créer ces 100 matchs corrects ? Je n'y arrive pas, j'arrive à faire en sorte que chaque équipe fasse bien une activité différente à chaque fois donc au bout de 10 tours elles ont toutes fait les 10 activités mais le 10 ème tour m'oblige toujours à faire rerecontrer une équipe..
En espérant que vous pourrez m'aider à créer le tournoi complet avec les 10 tours.
Merci d'avance
Bonne Journée
Si n est impair c'est possible.
Si n=2 c'est impossible. En regardant rapidement j'ai l'impression que c'est impossible aussi pour n=4 donc on peut penser que c'est impossible pour n pair mais je n'ai aucune certitude dans un sens ou dans l'autre.
Si je comprends bien le problème, avec les seules hypothèses de @Tournoi, il suffit de prendre les équipes par pairs et de faire faire à chaque pair les 10 activités. $\dfrac{20}{2} = 10$.
1) Chaque équipe apparaît une et une seule fois sur chaque ligne et sur chaque colonne.
2) Deux cases différentes ne peuvent pas contenir la même paire d'équipes.
Voici une solution pour $n$ impair. On divise l'ensemble des équipes en deux blocs $A_1,\ldots,A_n$ et $B_1,\ldots,B_n$. Sur la case $(i,j)$ on met le couple $(A_{2i+j},B_{i+j})$ (avec par convention $A_{n+1}=A_1$, $A_{n+2}=A_2$, etc.).
Ça marche car $2$ est inversible modulo $n$. Par contre la méthode ne marche pas pour $n$ pair car si on veut mettre $(A_{ai+bj},B_{ci+dj})$ sur la case $(i,j)$, pour que chaque équipe apparaisse une et une seule fois sur chaque ligne et chaque colonne on a besoin que $a,b,c,d$ soient inversibles modulo $n$, donc ils doivent être impairs, mais dans ce cas le déterminant $ad-bc$ est pair donc l'application $(i,j)\mapsto (ai+bj,ci+dj)$ n'est pas injective.
Sauf bien sûr s'ils doivent toujours être occupés :-).
Cordialement.
Explication. On part d'un carré gréco-latin d'ordre $2n$, où $n$ est le nombre de tours ou d'activités ; cela donne une façon de remplir un carré $n\times n$ par des couples $(i,j)$ de nombres de $1$ à $n$ de sorte que chaque couple apparaisse une et une seule fois.
En ajoutant $n$ aux nombres du deuxième carré, on décrit ainsi un calendrier de tournoi avec une contrainte/propriété supplémentaire, à savoir que les équipes $1$ à $n$ rencontrent chacune des équipes de $n+1$ à $2n$ une fois et une seule.
En Sage, qui sait produire de telles bestioles :
def allonge(e,l=2): return (l-len(str(e)))*' '+str(e) def presente(n): D = designs.mutually_orthogonal_latin_squares(2,n) ch = '' for r in range(n): ch+="Tour %s : " % allonge(r+1) for a in range(n): ch+= '%s-%s ' % (allonge(D[0][r,a]+1,len(str(n))),allonge(D[1][r,a]+n+1,len(str(n)))) ch+= "\n" return ch print presente(10)Bien sûr, cela ne lève pas l'impossibilité décelée par JLT. Entrée : Sortie :En fait c'est possible pour $2n$ quelque soit $n$. Cela revient à construire un graphe simple $n$-régulier à $2n$ sommets; ce qui est toujours possible.
Dans ce cas particulier @Tournoi doit construire un graphe d'ordre $20$, $10$-régulier.
Ce que je crois comprendre, suite aux posts de JLT et Math Coss. Il s'agit de trouver, pour $n=10$, deux carrés latins d'ordre $n$ qui sont orthogonaux. Cela existe si et seulement si $n \ne 2, 6$. Une construction explicite (pour $n$ pair, $n \ge 10$) figure dans l'article suivant https://ac.els-cdn.com/S0021869399978791/1-s2.0-S0021869399978791-main.pdf?_tid=63ef68fd-56b6-43ab-8428-9b7b4c2b8d50&acdnat=1534489322_c90129f0ebe01efc5fa3345343abd5fc, avec un mini-rappel historique en introduction. Voir aussi https://www.frisc.no/wp-content/uploads/2011/10/Chen-Talk_Bergen_2011.pdf où l'on croit comprendre que Gaston Terry (1900-1901) a occupé pendant deux ans ses week-end pour montrer la non-existence de deux carrés latins d'ordre 6 orthogonaux (on s'occupe comme on peut).
Rappel : un carré latin d'ordre $n$ est un carré $A = (a_{i,j})_{1 \le i,j \le n}$ où les $a_{i,j}$ vivent dans un ensemble $S$ (les symboles) de cardinal $n$, tel que chaque symbole figure une et une seule fois dans chaque ligne et chaque colonne. Deux carrés latins $A, B$ d'ordre $n$ sur le même ensemble $S$ de symboles sont dits orthogonaux si les $n^2$ couples $(a_{i,j}, b_{i,j})$ sont deux à deux distincts.
Par exemple, si $q$ est une puissance d'un nombre premier et $\F_q = \{a_1, \cdots, a_q = 0\}$ ``le corps'' à $q$ éléments, alors les $q-1$ carrés $A^{(a)} = (aa_i + a_j)_{1 \le i,j \le q}$, pour $a \in \F_q \setminus \{0\}$, sont des carrés latins d'ordre $q$ sont deux à deux orthogonaux. Autres exemples : pour $n$ impair, JLT a explicité deux carrés latins orthogonaux d'ordre $n$. Et Math Coss a montré deux carrés latins d'ordre 4 orthogonaux, puis d'ordre 10.
Sinon mon raisonnement sur l'existence est facile à comprendre si on en sait un peu sur la théorie des graphes.
le fait de dire qu'il existe un graphe $n$-régulier d'ordre $2n$ ou quoi ?
En fait, mon véritable problème, je l'avoue, c'est que je n'ai probablement pas compris la demande initiale de l'auteur du fil ! Je vois bien qu'en présence de deux carrés latins d'ordre $n$ orthogonaux, on peut résoudre la demande initiale, enfin ce que j'en ai compris. Mais peut-être que ce n'est pas nécessaire de disposer de tels carrés latins d'ordre $n$.
Une question pour toi. Je prends $n=2$ et le graphe $2$-régulier d'ordre 4 suivant (désolé pour le dessin).
$$
\xymatrix {
\bullet \ar@{-}@/^20pt/[rrr] \ar@{-}[r] &\bullet \ar@{-}[r] &\bullet \ar@{-}[r] &\bullet\\
}
$$
Comment organises tu un tournoi répondant à la spécification de l'auteur du fil ? i.e. en remplaçant son $n=10$ par $n=2$ ?
Cependant, il n'est pas suffisant d'avoir un graphe $n$-régulier avec $2n$ sommets. JLT a donné un contre-exemple ci-dessus. Pour le graphe $2$-régulier à quatre sommets $\{1,2,3,4\}$ dont les arêtes sont $\{1,2\}$, $\{2,3\}$, $\{3,4\}$, $\{4,1\}$, il n'est pas possible de faire un tournoi en deux tours dont les arêtes décrivent les rencontres sans qu'une des équipes ne répète une des activités.
En effet, si par exemple $1$ rencontre $2$ dans l'activité A au premier tour, $1$ doit passer à l'activité B au second tour et $2$ ne peut rien faire (elle a déjà fait l'activité A et l'activité B est occupé par une équipe déjà rencontrée).
Reste une question : bien qu'il n'existe pas deux carrés latins orthogonaux d'ordre $6$, peut-on organiser un tournoi avec 6 tours, 6 activités et 12 équipes ?
Edit : correction coquille sur les tailles problématiques pour les carrés bilatins (2 et 6) ; ce message répète en partie et répond en partie au précédent.
Suite à mon post et celui de Math Coss, peux tu, pour $n = 6$, à l'aide du graphe biparti complet $K_{6,6}$, à $2n = 12$ sommets et $6$-régulier, organiser un tournoi avec 6 tours, 6 activités et 12 équipes (je répète ainsi la question de Math Coss) ?
Dans notre cas .$10$ arêtes qui partent d'un sommet sont $10$ activités différentes.
Si tu veux, tu colores progressivement les arêtes; chaque couleur étant une activité.
Et comme dans un tel graphe, il y a $n^2$ arêtes et que dans notre histoire, il y a $n$ activités, là je m'incline.
Pour l'anecdote, le groupe des automorphismes de ce graphe est le $2$-groupe d'ordre $16$ engendré par $[(3,6)(4,X),\ (1,2)(7,8),\ (1,3,2,6)(4,7,X,8)(5,9),\ (1,4)(2,X)(3,8)(6,7)]$. Ça ne me saute pas aux yeux...
PS : Il y a deux orbites de sommets, $\{5,9\}$ et les huit autres ensemble. Je ne vois pas pourquoi $5$ et $9$ sont particuliers. Au moins, ça fait apparaître des puissances de $2$.
Au second tour $1$ rencontre $4$ dans l'activité B et $2$ rencontre $3$ dans l'activité B.
Je vois toujours pas le problème.
En fait quand on choisit une arête entre deux sommets, après on choisit une autre arête entre deux autres sommets jusqu'à $n$ arêtes pour un tour, puis on refait la même chose pour un second tour....ainsi de suite.
Conclusion : Compte tenu de l'existence de paires de carrés latins orthogonaux en toute dimension sauf $2$ et $6$ et de l'obstacle relevé par JLT pour $n=2$, nous pouvons conclure que le problème initial avec $n$ tours, $n$ activités et $2n$ équipes a des solutions pour toute valeur de $n$ sauf $n=2$.
PS : Pour trouver ce tournoi, j'ai utilisé un MILP, c'est-à-dire que j'ai fait résoudre un système linéaire à coefficients entiers dont les inconnues sont indexées par les tours, les activités et les paires d'équipes. Plus précisément, $A[r,a,e,f]=1$ si l'équipe $e$ rencontre l'équipe $f$ pendant le tour $r$ à l'activité $a$ (en imposant $e<f$). Les contraintes s'expriment assez facilement, il y a finalement 5184 inconnues et 246 équations – une paille pour Sage qui trouve une solution en moins d'une seconde !
T, At, E = 6, 6, 12 # tours, activités, équipes p = MixedIntegerLinearProgram() A = p.new_variable(binary=True) xA = p.new_variable(binary=True) for r in range(T): for a in range(At): p.add_constraint( add(A[r,a,e,f] for e in range(E) for f in range(e))<=1 ) for e in range(E): p.add_constraint( add(A[r,a,e,f] for f in range(e) for a in range(At))\ +add(A[r,a,f,e] for f in range(e+1,E) for a in range(At)) ==1 ) for e in range(E): for f in range(e): p.add_constraint( add( A[r,a,e,f] for r in range(T) for a in range(At)) <= 1) for a in range(At): p.add_constraint( add(A[r,a,e,f] for r in range(T) for f in range(E))\ +add(A[r,a,f,e] for r in range(T) for f in range(e+1,E)) <= 1) print "Nombre de variables : %s" % p.number_of_variables() print "Nombre de contraintes : %s" % p.number_of_constraints() def allonge(e): return (2-len(str(e)))*' '+str(e) def pres(R): ch = '' for i in range(At): ch+= 'Tour %s : ' % (i+1) for j in range(At): r = R[(i,j)] ch+= '%s-%s ' % (allonge(r[0]),allonge(r[1])) ch+= '\n' return ch p.solve() AA = p.get_values(A) D = AA.keys(); D.sort() Rep = {(a[0],a[1]): (a[3]+1,a[2]+1) for a in D if AA[a]!=0} print pres(Rep)Pour la bonne bouche, voici un dernier (?) tournoi pour 5, 5 et 10 produit par le script précédent : Le groupe d'automorphismes du graphe est d'ordre $16$ ; il y a deux orbites de sommets, $\{2,8\}$ et les autres ; on voit que $2$ et $8$ sont reliés à quatre sommets chacun, avec lesquels ils forment quatre triangles (par exemple $213$, $234$, $245$ et $251$). Ce n'est pas le même graphe que celui-ci (même les groupes d'automorphismes ne sont pas isomorphes).
Cordialement
Juste pour te dire que j'ai trouvé ta méthode astucieuse et je ne te cache pas que j'ai mis un petit moment pour comprendre ; en particulier, à cause des contraintes ``$=1$'' versus ``$\le 1$''. J'ai essayé de faire la même chose que toi (en copiant sur toi, donc) dans mon langage préféré. Petite variante cependant : je me suis alloué des variables $x_{t,a,I}$ où $t$ varie dans $T = [1..n]$ (les tours), $a \in A = [1..n]$ (les activités) et $I$ dans l'ensemble des paires d'éléments de $\{1..2n\}$ (les matchs possibles). Avec la même signification que toi : $x_{t,a,I} = 1$ si au tour $t$, et à l'activité $a$, on fait jouer $I$. Donc en tout $n^2 \binom{2n}{2}$ inconnues. Versus $5n^2 + \binom{2n}{2}$ inéquations/équations :
$$
\sum_I x_{t,a,I} \quad \buildrel {(1)} \over =\quad 1, \qquad\qquad
\sum_{a \in A\atop j, j \ne i} x_{t,a,\{i,j\}} \quad \buildrel {(2)} \over =\quad 1, \qquad\qquad
\sum_{t \in T\atop j, j \ne i} x_{t,a,\{i,j\}} \quad \buildrel {(3)} \over =\quad 1, \qquad\qquad
\sum_{t \in T \atop a \in A} x_{t,a,I} \quad \buildrel {(4)} \over \le \quad 1
$$
Les équations $(1)$ sont indexées par $T \times A$, il y en a $n^2$ ; cette équation raconte que pour chaque $(t,a)$, on veut un seul $I$ tel que ....etc.... Les équations $(2)$, elles sont indexées par les $(t,i) \in T \times \{1..2n\}$, il y en a $2n^2$ ; elles racontent ...etc...
J'ai juste un $\le 1$ pour le paquet $(4)$ de droite.
Mais manque de pot, le package Linear Programming de mon langage n'est absolument pas efficace. Regarde les temps de calculs pour $n= 5$ (sorry pour l'affichage, je ne suis pas cassé le c.l à faire un joli truc comme toi).
[color=#000000] n = 5 nombre d'inconnues : 1125 nombre d'équations : 170 Time: 52.520 state = 0 [ <{ 7, 8 }, { 1, 2 }, { 5, 6 }, { 3, 9 }, { 4, 10 }>, <{ 6, 10 }, { 3, 4 }, { 8, 9 }, { 1, 5 }, { 2, 7 }>, <{ 2, 5 }, { 9, 10 }, { 1, 4 }, { 6, 7 }, { 3, 8 }>, <{ 1, 3 }, { 6, 8 }, { 7, 10 }, { 2, 4 }, { 5, 9 }>, <{ 4, 9 }, { 5, 7 }, { 2, 3 }, { 8, 10 }, { 1, 6 }> ] [/color]Une question : quel logiciel te dessine les graphes ? Via Sage ?Voilà, voilà. Encore bravo pour ton idée.
Côté performances, Sage résout le problème pour $n=5$ en 0,3 s et pour $n=6$ en 1,3 s... Le paquet de programmation linéaire utilise par défaut le “solver” GLPK de GNU. C'est bien Sage qui dessine les graphes (G.show()) ; comme la disposition des sommets est un peu aléatoire, il faut parfois plusieurs invocations pour avoir un dessin « plus joli ».
Cela dit, cette méthode ne semble pas aboutir pour le problème initial avec 10 tours, 10 activités et 20 équipes parce que le système est trop gros.
On peut essayer de montrer l'impossibilité d'un carré bilatin de taille 6x6 (le problème des 36 cavaliers d'Euler). La contrainte qu'une équipe d'indice $\le n$ ne rencontre que des équipes d'indice $\ge n+1$ s'exprime par $A[t,a,i+n,i]=0$ pour $1\le t,a,i\le n$. [NB : en fait, les équipes sont indexées de $0$ à $n-1$ ; aussi, j'ai écrit plus haut $e<f$, en fait c'est $e>f$ qui est utilisé.]
Pour $n=5$, le système se résout en 0,2 s. Pour $n=7$, il faut environ 80 s. Pour $n=6$... eh bien, ça ne semble pas aboutir. Le solver ne trouve rien en 10 min mais il ne détecte pas qu'il n'y a pas de solution.
Autre tentative, en ajoutant un objectif au problème linéaire : minimiser $C=\sum_{t,a,i=1}^nA[t,a,i+n,i]$. Pour $n=5$, ça aboutit en 0,2 s. Pour $n=6$, ça ne semble rien donner en 10 min. Si j'ajoute "p.solver_parameter("mip_gap_tolerance",1)", il trouve en moins de 4 s une solution avec $C=8$. Comme je ne comprends pas trop ce que cela veut dire, je ne sais pas si cela suffit à montrer qu'il n'existe pas de solution avec $C=0$. (En fait non : avec $n=7$ et la même tolérance, on obtient une solution avec $C=14$ en 20 s et quelques, alors qu'il existe une solution avec $C=0$.)
Peut-être que l'histoire n'est pas complétement finie ? A un moment donné, j'ai pensé aux réseaux de transport et Ford-Fulkerson que je connais un peu. Juste penser, rien de plus.
Je n'ai pas regardé l'article de Marie-Nicole Gras (quelqu'un de chez nous, cocorico) https://ac.els-cdn.com/S0021869399978791/1-s2.0-S0021869399978791-main.pdf?_tid=e60beb8f-ad58-4173-a8ef-817068d4c321&acdnat=1534871826_8dc0dad66e3f6b5acb9ff4f5efd2a7f2 concernant la construction explicite de deux carrés latins d'ordre $n$ orthogonaux (pour $n$ pair, $n \ge 10$).
A quoi, je pense ? Imagine un instant que nous arrivions à mettre au point un petit programme simple et efficace permettant de générer, pour $n \ge 3$, un tournoi à $n$ tours, $n$ activités et $2n$ équipes avec la spécification que nous lui avons donnée. Tu te rends compte du pognon que l'on pourrait se faire ?
Blague à part, je n'ai aucune idée de la façon de procéder et même d'attaquer (pour des tailles de l'ordre de 307, le MILP serait complètement impuissant : 100.000 inconnues !).
$$
\F_q = \{a_1, \cdots, a_q\}, \qquad \qquad
C^ {(a)} = (aa_i + a_j)_{1 \le i,j \le q}, \quad a \in \F_q^*
$$
A droite, une famille de $q-1$ carrés latins, indexée par $\F_q^*$, et deux à deux orthogonaux.
Et que sera ma part du gâteau dans cette affaire ?
Passe leurs mes remerciements @JLT.
Je te rappelle que nous n'avons pas la même spécification du problème, toi et nous. La nôtre est la suivante : un $n$-tournoi est un carré $(I_{t,a})_{T \times A}$ avec $T = [1..n]$ (les tours), $A = [1..n]$ (les activités) et chaque $I_{t,a}$ est une partie à deux éléments de $\{1..2n\}$, le tout vérifiant :
$$
\bigcup_{a \in A} I_{t,a} = \{1..2n\} \hbox { pour chaque $t$}, \qquad
\bigcup_{t \in T} I_{t,a} = \{1..2n\} \hbox { pour chaque $a$}, \qquad
\hbox {les $n^2$ ensembles $I_{t,a}$ sont deux à deux distincts}
$$
La collection $(I_{t,a})$ est l'ensemble des arêtes d'un graphe $n$-régulier sur $\{1..2n\}$ mais pas n'importe quel graphe $n$-régulier de degré $2n$ (relire les posts de Math Coss à ce sujet).
Et il fallait s'y attendre : beaucoup de clients potentiels (j'ai commencé à démarcher selon les sages conseils de Math Coss) veulent un $n$-tournoi en exigeant un graphe parmi quelques graphes $n$-réguliers de leurs choix.
Bref, tout cela pour dire que nous avons besoin de définir un cahier des charges très serré, avec probablement une spécification formelle. Sans un tel cachier des charges, cela risque de partir dans tous les sens. Pas question de tomber dans le travers du coup de la balançoire.
Recevez mes encouragements !
Je me cite:
C'est juste après ce post que @Math Coss nous a sorti des carrés latins d'ordre $6$ orthogonaux..
Il ne peut pas jurer qu'il n'a pas utilisé mes explications. Si je ne fais pas partie des concepteurs, c'est que vous retenez ce que vous voulez.
C'est pas juste !
Je sais que t'es un gars fortiche (excuse cette familiarité), enfin je te considère comme tel. Peux tu essayer d'expliquer à qui tu sais que tu n'as PAS montré l'existence de deux carrés latins orthogonaux d'ordre 6 ? Enfin, si tu as le temps (et/ou l'envie). Moi j'y renonce.
Note : si c'était le cas (i.e. si tu avais montré l'existence ...), tu serais vraiment fortiche car cela contredirait les spécialistes Bose & Shrikande & Parker (en 1959, 1960) et également Dénes & Keedwell qui ont écrit en 1974 un ouvrage entier de plus de 500 pages (Latin Squares And Applications) https://books.google.fr/books/about/Latin_squares_and_their_applications.html?id=W2IPAQAAMAAJ&redir_esc=y
@Babacar : Tu n'est pas très attentif. Je n'ai pas utilisé tes explications mais visiblement, tu n'as pas utilisé les nôtres non plus... Je commence par des généralités sur les carrés latins, puis sur le problème du jour.
Un carré latin de taille $n$ est une matrice carrée dont les coefficients sont les éléments de $\{1,\dots,n\}$ : chaque coefficient doit apparaître une fois et une seule dans chaque ligne et chaque colonne. Par exemple, il existe exactement deux carrés latins d'ordre $2$ : $\left(\begin{smallmatrix}1&2\\2&1\end{smallmatrix}\right)$ et $\left(\begin{smallmatrix}2&1\\1&2\end{smallmatrix}\right)$.
Quand on a deux carrés latins, on peut les décrire par une matrice remplie de couples. Par exemple, les deux carrés latins précédents sont décrits par $\left(\begin{smallmatrix}(1,2)&(2,1)\\(2,1)&(1,2)\end{smallmatrix}\right)$.
Deux carrés latins sont dits orthogonaux si, dans la matrice précédente, chaque couple $(i,j)$ apparaît au plus une fois (et donc, exactement une fois). On voit que les deux carrés latins de taille $2$ ne sont pas orthogonaux puisque le couple $(1,2)$ apparaît deux fois. En revanche, les carrés latins d'ordre $3$ suivants : \[A=\begin{pmatrix}1&2&3\\2&3&1\\3&1&2\end{pmatrix}\ \text{et}\
B=\begin{pmatrix}3&1&2\\2&3&1\\1&2&3\end{pmatrix},\quad\text{décrits par}\
\begin{pmatrix}(1,3)&(2,1)&(3,2)\\(2,2)&(3,3)&(1,1)\\(3,1)&(1,2)&(2,3)\end{pmatrix},\]sont orthogonaux.
Un carré bilatin, c'est la même chose que deux carrés latins orthogonaux.
Théorème, énoncé par Euler et connu sous le nom de « problème des 36 cavaliers » : il n'existe pas de paire de carrés latins orthogonaux de taille $6$ – c'est-à-dire, pas de carré bilatin de taille $6$.
Le problème du jour, ce sont les tournois (le mot n'est pas standard ; ou plutôt, il y a un sens standard mais il est différent). Pour un tournoi de taille $n$, on a $n$ tours, $n$ activités et $2n$ équipes, que l'on numérote de $1$ à $2n$. Pour chaque tour et chaque activité, on veut désigner deux équipes, de sorte que :
- chaque équipe fasse un match à chaque tour ;
- chaque équipe fasse chaque activité une fois et une seule ;
- deux équipes données se rencontrent au plus une fois dans le tournoi.
Si on code les tours sur les $n$ lignes d'une matrice, les activités sur les $n$ colonnes, on veut remplir la matrice par des couples $(i,j)$ d'entiers entre $1$ et $2n$ de sorte que :Si on a deux carrés latins orthogonaux, disons deux matrices $A=(a_{kl})$ et $B=(b_{kl})$, on fabrique un tournoi en mettant en position $(k,l)$ le couple d'équipes $a_{kl},n+b_{kl}$. Par exemple, avec les deux carrés latins d'ordre $3$ ci-dessus, on fabrique le tournoi \[\begin{pmatrix}(1,6)&(2,4)&(3,5)\\(2,5)&(3,6)&(1,4)\\(3,4)&(1,5)&(2,6)\end{pmatrix}.\] Au premier tour, l'équipe 1 rencontre l'équipe 6 à l'activité 1 ; l'équipe 2 rencontre l'équipe 4 à l'activité 2 ; etc. Mais il existe des tournois qui ne proviennent pas de paires de carrés latins orthogonaux.
Fait (repéré pour commencer par JLT il y a deux ou trois semaines) : il n'y a pas de tournoi avec 2 tours, 2 activités et 4 équipes.
Fait : il existe des tournois pour toute autre valeur de $n$, y compris $n=6$. Si $n\ne6$, choisir deux carrés latins orthogonaux d'ordre $n$ (ça existe) et appliquer la procédure ci-dessus ; si $n=6$, prendre l'exemple calculé plus haut.
Bien sûr, je n'ai pas « sorti des carrés latins d'ordre 6 orthogonaux » parce que les coefficients de cette matrice sont entre $1$ et $12$ et pas entre $1$ et $6$. On ne peut pas partitionner $\{1,\dots,12\}$ en deux parties de cardinal $6$ pour construire deux carrés latins orthogonaux à partir de là.
Voici deux arguments. Le premier, c'est que c'est impossible et que tout le monde est d'accord là-dessus depuis Euler. Le second, c'est que quand on a un tournoi, on en déduit un graphe $6$-régulier sur $12$ sommets en ne retenant que les équipes qui s'affrontent et en oubliant à quel tour et à quelle activité. Or, quand on fabrique un tournoi à partir de deux carrés latins orthogonaux, le graphe sous-jacent est biparti : les équipes de $1$ à $n$ ne rencontrent que les équipes de $n+1$ à $2n$. Comme le graphe associé à cette matrice n'est pas biparti (il contient un triangle), c'est qu'il ne provient pas de carrés latins orthogonaux.
Pour résumer :
Le pognon dont parle Claude, je crois bien que c'est une boutade et qu'il n'y a ni acheteurs, ni rien à vendre de toute façon. Quant aux questions de paternité, ma foi, comme cette histoire ne sortira sans doute pas des colonnes du forum, les lectrices intéressées par la chose se feront leur idée en lisant ce fil : la seule nouveauté a été apportée par Sage !
Je ne comprends pas trop ici ; la notion de carrés latins orthogonaux dans sa définition dépend-elle des coefficients qui apparaissent ou tout simplement de la non répétition d'un couple.
5 & 2 & 4 & 1 & 3 \\
4 & 1 & 3 & 5 & 2 \\
3 & 5 & 2 & 4 & 1 \\
2 & 4 & 1 & 3 & 5\end{pmatrix}.\]
2) Une paire de carrés latins orthogonaux est rempli de couples $(i,j)$ avec $1\le i,j\le n$. Chaque $i$ et chaque $j$ apparaissent une fois et une seule sur chaque ligne et chaque colonne ; chaque couple apparaît une fois et une seule. Exemple : \[\begin{pmatrix}(1, 1)& (3, 4)& (5, 2)& (2, 5)& (4, 3)\\
(5, 4)& (2, 2)& (4, 5)& (1, 3)& (3, 1)\\
(4, 2)& (1, 5)& (3, 3)& (5, 1)& (2, 4)\\
(3, 5)& (5, 3)& (2, 1)& (4, 4)& (1, 2)\\
(2, 3)& (4, 1)& (1, 4)& (3, 2)& (5, 5)\end{pmatrix}.\]
3) Un tournoi est une matrice remplie de couples $(i,j)$ avec $1\le i,j\le 2n$ [pas tous : il n'y a que $n^2$ coefficients dans la matrice alors qu'il y a $4n^2$ couples possibles]. Chaque $i$ et chaque $j$ apparaissent une fois dans chaque ligne et chaque colonne. Un couple $(i,j)$ apparaît au plus une fois.
Exemple de tournoi qui provient des carrés latins orthogonaux précédents ($X=10$) : \[\begin{pmatrix}(1, 6)& (3, 9)& (5, 7)& (2, X)& (4, 8)\\
(5, 9)& (2, 7)& (4, X)& (1, 8)& (3, 6)\\
(4, 7)& (1, X)& (3, 8)& (5, 6)& (2, 9)\\
(3, X)& (5, 8)& (2, 6)& (4, 9)& (1, 7)\\
(2, 8)& (4, 6)& (1, 9)& (3, 7)& (5, X)\end{pmatrix}.\] Les 25 arêtes du graphe (biparti) associé à ce tournoi sont : \begin{align*}\bigl\{\{1, 6\},\ &\{3, 9\},\ \{5, 7\},\ \{2, X\},\ \{4, 8\},\ \{5, 9\},\ \{2, 7\},\ \{4, X\},\ \{1, 8\},\ \{3, 6\},\ \{4, 7\},\ \{1, X\},\ \{3, 8\},\\ & \{5, 6\},\ \{2, 9\},\ \{3, X\},\ \{5, 8\},\ \{2, 6\},\ \{4, 9\},\ \{1, 7\},\ \{2, 8\},\ \{4, 6\},\ \{1, 9\},\ \{3, 7\},\ \{5, X\}
\bigr\}.\end{align*}
Exemple de tournoi qui ne provient pas de deux carrés latins orthogonaux : \[\begin{pmatrix}(1,2)&(3,4)&(5,6)&(7,8)&(9,X)\\
(3,6)&(1,8)&(2,9)&(4,X)&(5,7)\\
(4,9)&(2,7)&(8,X)&(3,5)&(1,6)\\
(8,5)&(6,X)&(4,7)&(1,9)&(2,3)\\
(7,X)&(5,9)&(1,3)&(2,6)&(4,8)\end{pmatrix}.\] Les 25 arêtes du graphe (non biparti) correspondant sont : \begin{align*}\bigl\{\{1,2\},\ &\{3,4\},\ \{5,6\},\ \{7,8\},\ \{9,X\},\ \{3,6\},\ \{1,8\},\ \{2,9\},\ \{4,X\},\ \{5,7\},\ \{4,9\},\ \{2,7\},\ \{8,X\},\\& \{3,5\},\ \{1,6\},\ \{8,5\},\ \{6,X\},\ \{4,7\},\ \{1,9\},\ \{2,3\},\ \{7,X\},\ \{5,9\},\ \{1,3\},\ \{2,6\},\ \{4,8\}\bigr\}.\end{align*}