Problème de challenge sprotif !

[desbonns26]

Bonjour à tous,

Je suis confronté à un problème qui me paraissait simple à première vue mais qui s'avère être un vrai casse-tête...

Je dois organiser un évènement sportif respectant les règles ci-dessous :
- 8 équipes
- 5 sports différents (où deux équipes s'affrontent)
- toutes les équipes doivent pratiquer une et une seule fois tous les sports (donc 5 manches au total dans cette compétition)
- une équipe ne dois jamais jouer deux fois contre une autre équipe

Donc une équipe fera 5 parties sur 5 sports différents en rencontrant 5 équipes différentes et ne rencontrera pas 2 équipes.

Le problème, c'est qu'il m'est impossible de trouver un combinaison qui fonctionne, je me retrouve forcément dans le cas où un équipe fait deux fois le même sport ou rencontre deux fois la même équipe ...

Avez-vous un modèle ou une simulation Excel qui prouve que mon challenge sportif est réalisable avec ces paramètre ?

Merci et bon courage !

Simon

[beagle]

8 équipes appelées 1,2,3,4,5,6,7,8
5 sports = 5 rangées du tableau
(k,n) signifie l'équipe k rencontre l'équipe n

toutes les équipes font les 5 sports une seule fois =
1,2,3,4,5,6,7,8 dans chaque rangée

les équipes se rencontrent une seule fois, tous les (k,n),(n,k) n'existent qu'en un seul exemplaire, et pas de (k,k) non plus.

une soluce semble ètre:

(12)(36)(47)(58)
(14)(23)(57)(68)
(15)(24)(38)(67)
(16)(25)(34)(78)
(17)(26)(35)(48)

j'ai enlevé les virgules (12) = (1,2) = l'équipe 1 rencontre l'équipe 2.

[desbonns26]

Merci beagle pour ta réponse.

Cependant je crois que tu as oublié une des règles : chaque équipe ne doit pratiquer qu'une et une seule fois chaque sport.

As-tu moyen d'intégrer ce paramètre dans ta simulation ?

Simon

[fatal_error]

et pas de (k,k) non plus.

:happy2:

ok je sors -->[]

[beagle]

Merci beagle pour ta réponse.

Cependant je crois que tu as oublié une des règles : chaque équipe ne doit pratiquer qu'une et une seule fois chaque sport.

As-tu moyen d'intégrer ce paramètre dans ta simulation ?

Simon

Tu as mal lu le tableau,
chaque activité sportive est une rangée.
dans chaque rangée tu ne trouves qu'une seule fois une mème équipe, et tu trouves toutes les équipes, donc elles font toutes une fois (et une seule) une activité donnée.

le tableau est:
5 rangées = 5 activités sportives
4 colonnes = les matchs : 4 matchs de 2 équipes

[desbonns26]

OK en effet ça marche. C'est de ma faute j'ai oublié de préciser quelque chose. Il n'est pas possible de faire deux fois le même sport dans la même manche étant donné que je ne dispose que d'un seul terrain / sport.

En fait, moi je travail avec un tableau de ce type :

Code: Tout sélectionner

          Sport A   Sport B   Sport C   Sport D   Sport E
Manche 1   12   -   XX   XX   XX
Manche 2   36   57   -   XX   XX
Manche 3   47   68   XX   -   XX
Manche 4   58   23   XX   XX   -
Manche 5   -   14   XX   XX   XX

Sur chaque ligne je dois avoir toutes les équipes représentées, sur chaque colonne je dois également avoir toutes les équipes.
Le pB c'est que j'arrive à faire 4 manches et je suis bloqué à la 5eme...

J'espère que c'est un peu plus clair,

Merci,

Simon

[beagle]

OK, j'ai compris.
J'avais tout regroupé dans l'"ordre" de 1 à 8 juste pour la présentation.Mais je n'avais pas tous les 1 les uns en-dessous des autres.

Ce n'est pas sur que j'ai assez de degré de liberté néanmoins avec la méthode que j'ai employée.Je vais regarder cela, mais pas trop le temps ce jour et demain.
Sur mon point de départ cela ne pose pas de soucis,
mais la fin était manuelle,bricolée, non "naturelle", donc je ne sais pas ...

[beagle]

Après réflexion en mangeant,
plutot que de chercher à faire, et te faire plaisir,

il me semble peut-ètre plus facile de casser:
de démontrer par l'absurde que c'est impossible,
j'ai l'embryon du début ...

[beagle]

Mon sentiment est que tu ne trouves pas parce que c'est impossible.

J'ai bricolé quelques minutes à partir de ma première solution (et mème en amont), mais les degrés de liberté permis par le fait des absences=des trous,8 équipes sur du 5x5 qui permet du 10 équipes, absence d'ordre dans les rencontres, on a le sentiment de pouvoir jouer sur ces degrés de liberté,
mais cela me semble une illusion.

Intuitivement, et je ne saurais pas le prouver , si un telle configuration existait, alors on pourrait vraisemblablement former deux carrés latins orthogonaux de 5x5, sauf que les 5 trous ne peuvent représenter qu'un seul "pas", qu'un seul carré, impossibilité d'orthogonaliser deux parties de deux carrés latins sur cette mème structure.
Mais je n'ai pas les bases maths pour affirmer quoique ce soit.

[desbonns26]

Ok, merci d'avoir passé du temps sur ce problème !

Je pense que je vais simplifier le problème en ne faisant que 4 sports au lieu de 5...

Simon

[beagle]

zut j'ai effacé car j'ai cru à erreur sur le message de ce matin.
Je remets le message initial dès que possible,
me suis embrouillé tout seul ...

[beagle]

C'est le problème des structures obsessionnelles compulsives.
J'ai beau ètre sur un autre boulot, ce problème tourne tout seul en tache de fond.Et cela m'a envoyé un faux message d'erreur, donc j'ai effacé sans rien vérifier.Donc je reprends.

D'abord je n'ai pas mis un terme au problème, c'est peut-ètre possible,
je fais état de mes doutes.

Ensuite, oui c'est très facile à faire si 4x4 ou 5x5,
donc 4 manches de 4 matchs (huit équipes)
ou 5 manches de 5 matchs (10 équipes).
On prend deux carrés latins orthogonaux pour faire un carré eulérien.

Pour relancer?
Si vraiment c'est impossible en 5 manches 5-1 matchs,
à cause? justement de la faisabilité en 5x5,
inversons le problème,
il n' y a pas deux carrés latins orthogonaux de 6x6,
est-ce réalisable de faire 6 manches de 5 matchs (10 équipes)
est-ce raisonnable de dire à cause de l'impossibilité de le faire en 6x6?