Combinaison

[dudumath]

Bonjour, j'étais en train de me poser une question:

On considère 12 équipes, numérotée 1,2,...12 qui se rencontrent en 1 contre 1.

Il y a 6 épreuves et 6 horaires, pour que les rencontres se déroulent.

LE but est d'organiser les rencontres telles que:

Chaque équipe rencontre une autre équipe au plus une fois
Chaque équipe fait une rencontre et une épreuve par horaire
Chaque équipe doit faire les 6 épreuves.

Finalement, ce problème revient à considérer un tableau 6x6 dans lequel on inscrit des couples (a,b) avec a et b dans {1...12} tels que

chaque nombres compris entre 1 et 12 ne figurent qu'une fois sur une ligne, qu'une fois sur une colonne et que toutes les cases du tableau soient différentes.

Une telle organisation est -elle possible?(après beaucoup de test je n'y suis pas arrivé )
Si oui, pouvez vous m'en indiquer une qui marche.

Merci d'avance

[L.A.]

Bonjour.

J'avance une idée mais je n'ai rien de concret.

Ca marche avec 6 équipes se rencontrant sur 3 horaires avec 3 épreuves :
par exemple :

Epreuve : I , II , III
1e jour : (1,2),(3,4),(5,6)
2e jour : (3,5),(1,6),(4,2)
3e jour : (6,4),(5,2),(3,1)

peut être est il possible d'en déduire une solution pour 12 équipes, mais je n'en vois pas...

par contre ça ne marche pas avec 4 équipes, 2 horaires et 2 épreuves :
si le premier jour, (1,2) joue I et (3,4) joue II, alors le 2e jour 1 et 2 doivent jouer II donc se ré-affronter.

Bref je ne sais pas quoi en penser...

[Finrod]

J'ai vérifié cette méthode, ça ne marche pas à mon avis.

On peut aussi remarqué que ça ne marche jamais pour n=2 (4 équipes)... mais je ne vois pas de lien entre les cas n et n+1...

J'ai vérifié aussi que si su les douze équipes, il y en a 6 qui ne se rencontrent jamais, c'est impossible. Mais contrairement à ce que j'ai cru au début, ce n'est aussi qu'un cas particulier.

Il doit y avoir une façon adéquate d'aborder le problème.

[dudumath]

Alors je m'y suis pas mal penché dessus, et comme vous avez du le constater après plusieurs essais " au pif", ça ne marche pas vraiment...

En fait ça ne marche pas du tout!!!

J'ai esquissé une sorte de démonstration, je vais essayer de vous l'expliquer le mieux possible

[Finrod]

Excellente idée.

[dudumath]

Finalement, le problème revient, par permutation de lignes colonnes du tableau (qui ne changent rien au résultat final) à placer les équipes 7 à 12 dans des rencontres contre les équipes 1 à 6 disposées comme suit:

1----2----3----4----5----6

2----3----4----5----6----1

3----4----5----6----1----2

4----5----6----1----2----3

5----6----1----2----3----4

6----1----2----3----4----5

Car au final, on doit retrouver les 12 équipes (en particulier les 6 premières une seule fois par ligne et une seule fois par colonne).

On va supposer de plus que, comme l'équipe 6 va devoir rencontrer les équipes de 7 à 12,qu'elles les rencontrent dans l'ordre 7,8,9,10,11,12: on a alors cette disposition:

1----2----3----4----5----6/7

2----3----4----5----6/8--1

3----4----5----6/9--1----2

4----5---6/10--1----2----3

5---6/11--1----2----3----4

6/12-1----2----3----4----5

On considère maintenant l'équipe 7:

Elle ne peut figurer ni sur la 1ère ligne ni sur la dernière colonne.
il faut alors la placer 5 fois avec les meme regles dans le tableau 5x5 extrait du tableau 6x6 en ayant supprimé 1ère ligne et dernière colonne i.e:

2----3----4----5----6/8

3----4----5----6/9--1

4----5---6/10--1----2

5---6/11--1----2----3

6/12-1----2----3----4

On considère la dernière ligne, ou il y a 4 possibilités pour placer le 7.
On va arbitrairement choisir de faire rencontrer 1 et 7 (reprenez la démonstration avec les autres cas possibles(2/7, 3/7,4/7) si vous en êtes pas convaincu, mais c'est la même chose):

On a alors:

2----3----4----5----6/8

3----4----5----6/9--1/7

4----5---6/10--1----2

5---6/11--1----2----3

6/12-1----2----3----4

Alors, on ne peut plus placer de 7 dans la 2nde ligne et la dernière colonne du nouveau tableau, il reste donc à placer un 7 dans le sous tableau 4x4 extrait du tableau 5x5 sans la 2ème ligne et dernière colonne i.e:

2----3----4----5

4----5---6/10--1

5---6/11--1----2

6/12-1----2----3

De plus, 7 ayant déja rencontré 1, il ne peut plus le rencontrer.
Sur la dernière colonne il reste 2 possibilités pour une rencontre avec 7: 2 ou 3, on choisit arbitrairement le 2, mais c'est pareil si on avait choisit 3, je vous laisse le soin de vérifier si vous le voulez.

On obtient donc:

2----3----4----5

4----5---6/10--1

5---6/11--1----2/7

6/12-1----2----3

et le 7 ne peut plus être placer sur la dernière colonne ni sur la 3ème ligne, donc il reste à placer 7 dans le sous tableau 3x3 sans la derniere colonne ni la 3eme ligne, i.e:

2----3----4

4----5---6/10

6/12-1----2

Le 7 a de plus déja rencontrer le 2, il faut donc le faire rencontrer le 4 sur la dernière colonne, on obtient:

2----3----4/7

4----5---6/10

6/12-1----2

Puis par le même raisonnement, il reste à placer 2 7 dans :

4----5

6/12-1

Evidemment le 5 rencontrera le 7, et finalement il est impossible de mettre un 7 sur la 1ère ligne.



En reprenant cette démonstration avec 8, 9,10, 11, 12 et en traitant tous les cas intermédiaires possibles(i.e a chaque fois qu'on choisit arbitrairement une équipe plutôt qu'une autre), on a balayé toutes les possibilités et on a montré que c'était impossible.



Voila tout!

Cordialement

[Finrod]

Il y a un problème je crois. Tout va bien sauf la première phrase. Il est tout à fait possible qu'on ne soit pas dans une situation ou 6 équipes en rencontre 6 autres...

Il me semble qu'il peut y avoir chassé croisé entre les équipes.


sinon après ok, ce cas là est impossible.

[beagle]

dudumath a raison, il s'agit de trouver deux carrés latins orthogonaux de 6,
ce qui n'existe pas.
de chaque couple d'équipe on peut prendre un exemplaire au hasard,
abcdef,
ils seront sur une seule colonne et une seule rangée, (=une épreuve de chaque, un horaire de chaque,
il faut les placer sur un carré latin.
Leur couple ghijkl obeissent à la mème règle, nouveau carré latin.

la troisième condition une seule rencontre entre deux équipes oblige à prendre des carrés latins orthogonaux.

En ordre 6 cela n'existe pas.Problème d'Euler ...

[beagle]

il me semble suspect de pouvoir choisir abcdef autant de fois que cela de manière aléatoire.On retomberait sur quasi l'ensemble (permuations) des carrés latins?
c'est l'orthogonalité qui serait fausse?
Zut, trop mal au crane aujourd'hui.Faut que je revois ça avec des exemples.
Entre la migraine et le boulot (si, si aussi un peu quand mème)...

[dudumath]

beagle, au final tu ne les choisis pas de manière si aléatoire, car finalement il "suffit" de tester les autres cas, et on sait pertinemment que choisir l'une ou l'autre ne changera pas grand chose ( on peut dire merci a Euler de nous avoir aiguiller cependant..., mais je crois que quelqu'un la démontré en testant toutes les combinaisons possibles, ce qui doit être assez fastidieux....)

[beagle]

ce qui me perturbe, c'est que les deux carrés latins reviennent à deux ensembles de droites parallèles qui vont se couper,
je ne devrais pas pouvoir mélanger autant de droites parallèles que m'autoriserait mon tirage aléatoire,
je sais , c'est pas clair,
c'est un truc dans ma tète,
faut que je regarde avec ordre 5 ou 7, donc 10 ou 14 équipes,...

[beagle]

OK,j'ai vérifié la grosse bétise que j'ai racontée.
Avec deux carrés latins de 5x5 on construit bien l'exo.
Et c'est totalement faux que de prendre aléatoirement abcde dans les couples fait un carré latin.
C'est heureusement faux.
Donc si carrés latins orthogonaux possibles pour n, le truc est plié,ça marche.
Mais pas prouvé par moi que c'est nécessairement carrés latins pour arriver à un résultat.

[beagle]

donc?
en fait?
si 1 est une seule fois par colonne, et une seule fois par rangée,
1 peut ètre considéré comme appartenant à un carré latin dont je cherche les autres éléments.
Si 2 rencontre 1, 2 doit appartenir à un carré latin orthogonal à 1.
Si 2 ne rencontre pas 1, 2 parallèle à 1, 2 est dans le mème carré latin que 1.
etc...
ce n'est pas démonstration, mais c'est sur que les couples d'équipes doivent venir de carrés latins orthogonaux.
Si on prend 1, alors tous les couples 1a, 1b, 1c, 1d, 1e, 1f permettent de trouver le carré latin a, b, c, d, e, f.
Et non pas au hasard des couples comme je l'avais bètement raconté,
mais qui m' a heureusement rapidement chiffonné.

Maintenant c'est peut-ètre faux.

[fatal_error]

salut,

voila une solution :
(1,2)--(3,4)--(5,6)--(7,8)--(9,10)--(11,12)
(3,4)--(1,2)--(7,8)--(5,6)--(11,12)--(9,10)
(5,6)--(7,8)--(9,10)--(11,12)--(1,2)--(3,4)
(7,8)--(5,6)--(11,12)--(9,10)--(3,4)--(1,2)
(9,10)--(11,12)--(1,2)--(3,4)--(5,6)--(7,8)
(11,12)--(9,10)--(3,4)--(1,2)--(7,8)--(5,6)

Chaque equipe est présente qu'une seule fois par colonne et par ligne.
Aucune equipe ne saffronte toute seule.

Pas beaucoup de mérite, prolog a fait tout le boulot.

Edit: on remarque beaucoup de permutation. Par ailleurs, la matrice est symétrique.

[beagle]

merci fatal error,
je regarde cela demain,
était encore faux dans mon texte si 1 ne coupe pas deux,alors ...
c'était bien sur faux, encore une fois,
et finrod avait raison, était génant de faire que deux groupes,
mais je ne savais pas si possible vraiment autrement.

[beagle]

rapidos, tu as deux fois les mèmes rencontres, je vois plusieurs couples (1,2) par exemple,
cela ne respecte pas la première condition.
Bon, moi c'est dodo.

[beagle]

je reste sur obligation de deux carrés latins.
Si je prends l'élément a du premier couple (a,b),
alors à coté je vais placer un couple (c,d).
Si c ne fait pas partie du carré latin de a, alors je ne pourrais plus remplir le carré avec d'autres lettres disposées en un seul élément par ligne et colonne.
Donc si d est idem avec a sur deux carrés latins, je ne peux plus disposer d'autres lettres pour remplir.
Donc a connu, dans le couple (c,d) un des éléments appartient au mème carré latin.
Et tout couple (x,y) est nécessairement orienté appartenant à deux carrés latins différents.

Bon, dans une heure je dis que c'est faux, mais c'est proche quand mème.
bien sur un exemple ne répondant pas à mes critères cloturerait plus vite la discussion.

[beagle]

soit (a,b) le premier couple,et (c,d) celui à coté.
Si a , c et d sont disposés sur trois carrés latins différents, alors il sera impossible de trouver une disposition d'un élément par colonne et par ligne pour les lettres e f g h i j k l .
il y a nécessicité de deux carrés latins et donc d'une orientation des couples.

[Finrod]

Chapeau fatal.

J'avais rien compris au carré latin, je ne connais pas.

[beagle]

si il y a plusieurs fois le couple (1,2) c'est que ces équipes s'affrontent plusieurs fois.
Ce qu' a mis fatal error ne convient pas.

dans l'énoncé:
"Chaque équipe rencontre une autre équipe au plus une fois"

Nécessité de deux carrés latins
et orthogonaux,
ce qui n'existe pas avec l'ordre 6.
Je change d'avis après le contre-exemple.