12 équipes et 6 lieux, les équipes ne doivent se croiser qu'

par **Keut** » 28 Avr 2015, 17:03

Bonjour,

Mon problème est le suivant :

Pour un jeu de piste, 12 équipes (EA à EL) doivent passer dans 6 lieux (L1 à L6) sans jamais croiser deux fois la même équipe.

Chaque équipe rencontre donc une nouvelle équipe dans le lieu suivant.

Je n'arrive pas a faire un planning correct.

Par exemple, léquipe A et B commence dans le lieu 1, C et D commencent dans le lieu 2,... Léquipe A parcours les sites dans l'ordre de 1 à 6, ensuite ça se complique:
#####| L1 | L2 | L3 | L4 | L5 | L6
TEAM A | H1 | H2 | H3 | H4 | H5 | H6
TEAM B | H1 | H? | H? | H? | H? | H?
TEAM C | H? | H1 | H? | H? | H? | H?
TEAM D | H? | H1 | H? | H? | H? | H?
.....

Les chiffres dans le tableau correspondent au créneau horaire (de H1 à H6)

Seul le résultat compte mais je suis également curieux de connaitre la méthode utilisée.

Merci pour votre aide.

Keut

par **Mathusalem** » 28 Avr 2015, 18:41

Est-ce une condition stricte ? Je ne suis pas sûr que ce soit possible. Algorithmiquement c'est possible de réduire le nombre de double rencontres, mais pas certain que ce soit possible de les éliminer.

par **Keut** » 28 Avr 2015, 18:52

Mathusalem a écrit:Est-ce une condition stricte ? Je ne suis pas sûr que ce soit possible. Algorithmiquement c'est possible de réduire le nombre de double rencontres, mais pas certain que ce soit possible de les éliminer.

Bonjour Mathusalem, merci de l'intêret que tu portes à mon problème.

Oui c'est une condition stricte.

En effet je ne suis pas sur que cela soit possible mais je veux bien une preuve. :lol3:

par **nodjim** » 28 Avr 2015, 19:17

Par exemple:
H1: (1,2)(3,4)(5,6)(7,8)(9,10)(11,12)
H2:(1,3)(2,5)(4,9)(6,8)(7,12)(10,11)
H3:(1,4)(3,8)(2,12)(5,9)(6,10)(7,11)
H4:(1,5)(3,9)(2,4)(6,7)(10,12)(8,11)
H5:(1,12)(3,10)(4,7)(5,8)(2,9)(6,11)
H6:(1,7)(3,11)(4,12)(5,10)(2,6)(8,9)

Les rencontres:
1:2,3,4,5,12,7
2:1,5,126,4,9
3:1,4,8,9,10,11
4:1,2,3,7,9,12
5:1,2,6,8,9,10
6:2,5,7,8,10,11
7:1,4,6,8,11,12
8:3,5,6,7,9,11
9:2,3,4,5,8,10
10:3,5,6,9,11,12
11:3,6,7,8,10,12
12:1,2,4,7,10,11

par **Mathusalem** » 28 Avr 2015, 19:24

nodjim a écrit:Par exemple:
H1: (1,2)(3,4)(5,6)(7,8)(9,10)(11,12)
H2:(1,3)(2,5)(4,9)(6,8)(7,12)(10,11)
H3:(1,4)(3,8)(2,12)(5,9)(6,10)(7,11)
H4:(1,5)(3,9)(2,4)(6,7)(10,12)(8,11)
H5:(1,12)(3,10)(4,7)(5,8)(2,9)(6,11)
H6:(1,7)(3,11)(4,12)(5,10)(2,6)(8,9)

Les rencontres:
1:2,3,4,5,12,7
2:1,5,126,4,9
3:1,4,8,9,10,11
4:1,2,3,7,9,12
5:1,2,6,8,9,10
6:2,5,7,8,10,11
7:1,4,6,8,11,12
8:3,5,6,7,9,11
9:2,3,4,5,8,10
10:3,5,6,9,11,12
11:3,6,7,8,10,12
12:1,2,4,7,10,11

Le 1 fait 6 fois la même épreuve

.. Il y a un ordre vertical dans le tableau

par **Keut** » 28 Avr 2015, 19:42

Merci nodjim!

Cependant je pense que tu n'as résolu qu'une partie du problème : les rencontres.
Je ne vois pas dans quel lieu se passe ces rencontres...

Chaque équipe doit passer dans les 6 lieux (c'est un jeu de piste).

Si je prends la première partie de ta réponse et que je suppose que l'axe x correspond au lieux de rencontre alors le problème est que l'équipe 1 reste dans le lieu 1...

Si j'inverse les axes, l'équipe 1 ne peut pas être à 6 endroits en même temps...

Qu'en penses tu? Est ce faisable?

par **Ben314** » 29 Avr 2015, 12:13

Salut,
0 1 2 3 4 5
0 2 5 1 3 4
0 3 1 4 5 2
0 4 3 5 2 1
0 5 4 2 1 3
1 0 3 2 5 4
1 2 0 5 4 3
1 3 4 0 2 5
1 4 5 3 0 2
2 1 4 5 3 0
3 4 2 1 5 0
4 5 2 0 3 1

Remarque : les équipes ne se rencontrent pas toutes, par exemple la 1 ne rencontre jamais la 6...

par **Ben314** » 29 Avr 2015, 12:26

Salut,
Une solution :
1 2 3 4 5 6
1 3 6 2 4 5
1 4 2 5 6 3
1 5 4 6 3 2
1 6 5 3 2 4
2 1 4 3 6 5
2 3 1 6 5 4
2 4 5 1 3 6
2 5 6 4 1 3
3 2 5 6 4 1
4 5 3 2 6 1
5 6 3 1 4 2

Remarque : les équipes ne se rencontrent pas toutes, par exemple la 1 ne rencontre jamais la 6...

par **Mathusalem** » 29 Avr 2015, 14:16

Pour chaque poste, au nombre de 6, il y a un couple d'équipes, numérotées de 1 a 12.

En 6 étapes, il faut que chaque équipe ait visité chaque poste, et n'ait jamais croisé une équipe 2 fois. Et il faut que chaque poste soit occupé ?
C'est comme ça que je comprends l'énoncé. Dans ta solution Ben314, tu as 5 équipes au poste 1 en même temps. Je sais pas si c'est la solution que cherche keut

par **Ben314** » 29 Avr 2015, 16:12

Mathusalem a écrit:C'est comme ça que je comprends l'énoncé. Dans ta solution Ben314, tu as 5 équipes au poste 1 en même temps. Je sais pas si c'est la solution que cherche keut

Ben, moi, je suis un vrai matheux bien con : l'énoncé, c'est ce qu'on me donne, ni moins, ni plus...

par **beagle** » 29 Avr 2015, 16:21

la solution devrait ètre un carré de 6x6
6 lieux, 6 dates (jour d'épreuves)
dans ce 6x6 un couple.

Dès lors cela ressemble aux 6 officiers d'Euler, problème connu comme étant impossible.
Car chaque équipe ne doit ètre qu'une seule fois dans une rangée = un lieu,
et une seule fois dans colonne = un jour d'épreuve.

Il n'y a pas de carrés latins d'ordre 6:
http://fr.wikipedia.org/wiki/Carr%C3%A9_gr%C3%A9co-latin

par **nodjim** » 29 Avr 2015, 18:58

D'accord avec Beagle pour la reformulation du problème. Je ne connaissais pas l'impossibilité de créer un tel carré, et le plus étonnant est que c'est encore une conjecture !
C'est plutôt vache comme problème...

12 équipes et 6 lieux, les équipes ne doivent se croiser qu'

12 équipes et 6 lieux, les équipes ne doivent se croiser qu'

Qui est en ligne