Exercices Alternatifs

Tournois et relations d’ordre

\begin{matrix}c \\ ◯ \end{matrix}2002 Vincent Guirardel (copyleft LDL : Licence pour Documents Libres).

     Source: tournoi.tex.

Version imprimable: tournoi.pdf

Théorie des ensembles, et structures de base. DEUG première année. Angle pédagogique : Ludique.

Objectifs et commentaires. Cet exercice essaye de questionner ce qu’est un ordre, et comment on peut faire un classement. En toile de fond, il y a le probleme d’un algorithme de tri. Les étudiants sont parfois surpris que l’équipe médaillée d’argent n’est pas forcément la deuxième meilleure. Le fait de se poser la question de la validité de l’hypothèse que les équipes sont totalement ordonnées amène à se poser la question de la définition de l’ordre.

Question 1. Tournoi standard.

Supposons qu’il y ait 4 équipes à départager. Après un éventuel tirage au sort, le calendrier des matches est le suivant. 1ère demi-finale : l’équipe A rencontre l’équipe B ; 2ème demi-finale : l’équipe C rencontre l’équipe D. Ensuite, la finale des perdants oppose les deux perdants des 2 demi-finales, et la finale oppose les gagnants des 2 demi-finales. Finalement, on distribue des médailles : or et argent pour le gagnant et le perdant de la finale, bronze et chocolat pour le gagnant et le perdant de la finale des perdants.

On suppose qu’il existe une relation d’ordre total ≤ entre les 4 équipes, de sorte que si deux équipes E, E′ sont telles que E < E′, alors le match de E contre E′ sera remporté par E′.

Peut-on être sûr que l’équipe médaillée d’or est supérieure aux autres ? De même, peuton être sûr que l’équipe médaillée d’argent est supérieure à celles médaillées de bronze et de chocolat ? Peut-on être sûr que l’équipe médaillée de chocolat est inférieure aux autres ?

Par ailleurs, pensez-vous que l’existence d’une telle relation d’ordre soit réaliste (voir aussi la question 2) ?

Question 2. Tournoi exotique.

Certains organisateurs de tournois sont des originaux : les tableaux suivants montrent trois de ces tournois dans lesquels 6 équipes se sont rencontrées. Les tableaux contiennent les gagnant de chaque match : par exemple, si A a gagné contre B (comme dans le tournoi 2), alors à la colonne A, ligne B on notera A (le signe - signifie qu’il n’y a pas eu de match entre les 2 équipes).

Pour chacun des trois tournois, déterminer s’il existe un ordre total comme dans la question précédente qui détermine l’issue du match. S’il en existe, le tournoi permet-il de le déterminer ? Sinon, donner tous les ordres possibles compatibles avec le résultat du tournoi. S’il n’existe pas d’ordre compatible avec les résultats du tournoi, expliquer pourquoi.

Tournoi 1 A B C D E F
A * - C D - -
B - * B - - F
C C B * - C C
D D - - * E D
E - - C E * E
F - F C D E *

Tournoi 2 A B C D E F
A * A A D - A
B A * C - - -
C A C * - E -
D D - - * D -
E - - E D * E
F A - - - E *
Tournoi 3 A B C D E F
A * - C - - -
B - * - D B F
C C - * - - -
D - D - * - D
E - B - - * -
F - F - D - *

Question 3. Préordre et équipes équivalentes.

Supposons qu’à l’issue d’un tournoi, il n’existe pas d’ordre sur l’ensemble des équipes qui détermine l’issue des matches. On dit qu’une équipe e′ est apparemment meilleure que e (et on note e ≺ e′) si il existe des équipes e_{1}, …, e_{n} telles que e a perdu un match contre e_{1} qui a perdu un match contre e_{2} qui a perdu un match contre e_{3}, etc. et e_{n} a perdu un match contre e′ (on considère qu’une équipe e est apparemment meilleure qu’elle même : e ≺ e). On dira que deux équipes e et e′ sont équivalentes si e ≺ e′ et e′ ≺ e.

Montrer que la relation ≺ est une relation de pré-odre, c’est à dire qu’elle est transitive et réflexive. Donner un exemple où elle n’est pas anti-symétrique.

Montrer que la relation ¡¡e et e′ sont équivalentes¿¿ est une relation d’équivalence. Quelles ses classes d’équivalences dans le premier tournoi ?

a. Démontrer le résultat suivant :

(i) Si ≺ est une relation de pré-ordre sur un ensemble, alors la relation ∼ définie par

x ∼ y ⟺ x ≺ y et y ≺ x

est une relation d’équivalence.

(ii) De plus, si X et Y sont deux classes d’équivalences pour la relation ∼, si il existe x ∈ X et y ∈ Y tels que x ≺ y, alors pour tout x′ ∈ X et tout y′ ∈ Y, on a x′ ≺ y′; proposer alors une définition pour une relation (entre les classes déquivalence) qu’on noterait X ≺ Y. (iii) Démontrer que la relation X ≺ Y définie au dessus est une relation d’ordre sur l’ensemble des classes d’équivalences de ∼.

b. Que peut-on déduire du résultat précédent à propos des classes d’équivalence dans un tournoi ?