Niveau doctorat

tournoi et graphe

Posté par
ludomaths 02-01-20 à 21:14

Bonjour

J' ai une question concernant l'organisation d'un tournoi.
Si j'ai n équipes qui doivent toutes se rencontrer et que chaque rencontre dure 1h, quelle est le nombre d'heures minimales pour que toutes les rencontres aient lieu ?

Cela revient à travailler avec un graphe complet et pour n pair, je trouve n-1 heures par permutation mais pour n impair, je sèche.

Si quelqu'un peut m'aider, merci d'avance.

**forum modifié**

Posté par re : tournoi et graphe 02-01-20 à 21:19

bonsoir

je vais répondre peut-être une bêtise, mais moi j'aurais dit :
2 parmi n, non ?

Posté par re : tournoi et graphe 02-01-20 à 21:26

Bonsoir Malou,
Merci pour ta réponse
2 parmi n correspond au nombre d'arêtes de mon graphe mais deux arêtes non incidentes peuvent représenter 2 "matchs" du tournoi qui peuvent se dérouler en même temps donc je pense que c'est moins.

Posté par re : tournoi et graphe 02-01-20 à 23:45

Dans le cas où on a un nombre n impair d'équipes.
Regardons l'équipe n°1
Pour rencontrer les n-1 autres équipes, elle a besoin de jouer n-1 matches ; il faut donc au moins n-1 matches.

Mais.
Quand on commence la mise en place, on a (n-1)/ matches pendant la 1ère heure, on a n-1 équipes qui jouent, et une équipe qui est en stand-by.
Cette équipe aura besoin, comme n'importe quelle autre, de n-1 heures pour rencontrer tous les adversaires.
n-1 heures, plus 1 heure à attendre au début, il faut donc n heures.

n heures, c'est le minimum, mais est-ce que ça suffit ?

Oui.

On va imaginer une (n+1)ième équipe, une équipe relais, fictive. On a donc maintenant n+1 équipe, dont une est fictive. n+1 est pair.
Pour que toutes les équipes se rencontrent (y compris, toutes les équipes rencontrent cette équipe relais), tu as déjà traité le cas, il suffit de n heures.

Au moins n heures, au plus n heures... la réponse est donc n heures.