\Annee{2002}
\Titre{Tournois et relations d'ordre}
\Auteur{Vincent \textsc{Guirardel}}


\Date{2002/12/04} % Format AAAA/MM/JJ. pour le 5 mars 2001: \Date{2001/03/05}

\Niveau{\DEUGi} %Le niveau principal. Typiquement: \DEUGi (=1ere annee), \DEUGii (=2eme annee), \Licence, ...

\AnglePedagogique{\Ludique} %l'angle pedagogique principal. Typiquement: \AQuoiCaSert, \Experimental, ...

\AnglesSecondaires{\Decouverte} %Eventuellement, les angles pedagogiques secondaires separes par des virgules

\Theme{\Ensembles} %Theme principal. Typiquement: \AlgLin, \Suites, \Series, ...
\ThemesSecondaires{Relations d'ordre}

\Objectif{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 \'etudiants sont parfois surpris que
l'\'equipe m\'edaill\'ee d'argent n'est pas forc\'ement la deuxi\`eme meilleure.

Le fait de se poser la question de la validit\'e de l'hypoth\`ese que les \'equipes sont totalement ordonn\'ees
am\`ene \`a se poser la question de la d\'efinition de l'ordre.
} % Partie objectifs et commentaires.


\begin{exo}

\qst{Tournoi standard.} Supposons qu'il y ait 4 \'equipes \`a d\'epartager.
Apr\`es un \'eventuel tirage au sort, le calendrier des matches est le suivant.
1\`ere demi-finale: l'\'equipe A rencontre l'\'equipe B; 2\`eme demi-finale: l'\'equipe C rencontre l'\'equipe 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\'edailles: 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 $\leq$ entre les $4$ \'equipes, de sorte que si deux \'equipes $E,E'$ sont telles
que $E< E'$, alors le match de $E$ contre $E'$ sera remport\'e par $E'$.

Peut-on \^etre s\^ur que l'\'equipe m\'edaill\'ee d'or est sup\'erieure aux autres~?
De m\^eme, peut-on \^etre s\^ur que l'\'equipe m\'edaill\'ee d'argent est sup\'erieure \`a celles m\'edaill\'ees de bronze et de chocolat~?
Peut-on \^etre s\^ur que l'\'equipe m\'edaill\'ee de chocolat est inf\'erieure aux autres~?

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


\qst{Tournoi exotique.} Certains organisateurs de tournois sont des originaux: les tableaux suivants
montrent trois de ces tournois dans lesquels 6 \'equipes se sont rencontr\'ees.
Les tableaux contiennent les gagnant de chaque match: par exemple, si A a gagn\'e contre B (comme dans le tournoi 2), alors
\`a la colonne A, ligne B on notera A (le signe - signifie qu'il n'y a pas eu de match entre
les 2 \'equipes).

Pour chacun des trois tournois, d\'eterminer s'il existe un ordre total comme dans la question pr\'ec\'edente qui d\'etermine
l'issue du match. S'il en existe, le tournoi permet-il de le d\'eterminer~? 
Sinon, donner tous les ordres possibles compatibles avec le r\'esultat du tournoi. 
S'il n'existe pas d'ordre compatible avec les r\'esultats du tournoi, expliquer pourquoi.

\begin{center}
\begin{tabular}{|r|cccccc|}
\hline
Tournoi 1& A&B&C&D&E&F\\
\hline
A&*&-&C&D&-&-\\
B&-&*&B&-&-&F\\
C&C&B&*&-&C&C\\
D&D&-&-&*&E&D\\
E&-&-&C&E&*&E\\
F&-&F&C&D&E&*\\
\hline
\end{tabular}\hfill
\begin{tabular}{|r|cccccc|}
\hline
Tournoi 2& A&B&C&D&E&F\\
\hline
A&*&A&A&D&-&A  \\
B&A&*&C&-&-&-\\
C&A&C&*&-&E&-\\
D&D&-&-&*&D&-\\
E&-&-&E&D&*&E\\
F&A&-&-&-&E&*\\
\hline
\end{tabular}
\\
\vspace{0.3cm}


\begin{tabular}{|r|cccccc|}
\hline
Tournoi 3& A&B&C&D&E&F\\
\hline
A&*&-&C&-&-&-  \\
B&-&*&-&D&B&F\\
C&C&-&*&-&-&-\\
D&-&D&-&*&-&D\\
E&-&B&-&-&*&-\\
F&-&F&-&D&-&*\\
\hline
\end{tabular}
\end{center}

\qst{Pr\'eordre et \'equipes \'equivalentes.}
Supposons qu'\`a l'issue d'un tournoi, il n'existe pas d'ordre sur l'ensemble des \'equipes
qui d\'etermine l'issue des matches. On dit qu'une \'equipe $e'$ est \emph{apparemment meilleure} que $e$
(et on note $e\prec e'$) si il existe des \'equipes $e_1,\dots,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\`ere qu'une \'equipe $e$ est apparemment meilleure qu'elle m\^eme: $e\prec e$).
On dira que deux \'equipes $e$ et $e'$ sont \emph{\'equivalentes}
si $e\prec e'$ et $e'\prec e$.

Montrer que la relation $\prec$ est une relation de pr\'e-odre, c'est \`a dire qu'elle est
transitive et r\'eflexive. Donner un exemple o\`u elle n'est pas anti-sym\'etrique.

Montrer que la relation <<\emph{$e$ et $e'$ sont \'equivalentes}>> est une relation d'\'equivalence.
Quelles ses classes d'\'equivalences dans le premier tournoi ?

\sq D\'emontrer le r\'esultat suivant:
\begin{quote}
(i)  Si $\prec$ est une relation de pr\'e-ordre sur un ensemble, alors la relation
$\sim $ d\'efinie par
$$x\sim y\iff x\prec y \text{ et } y \prec x$$
est une relation d'\'equivalence. 

(ii) De plus, si $X$ et $Y$ sont deux classes d'\'equivalences pour la relation $\sim$,
si il existe $x\in X$ et $y\in Y$ tels que $x\prec y$, alors pour tout $x'\in X$ et tout $y'\in Y$,
on a $x'\prec y'$; proposer alors une d\'efinition pour une relation (entre les classes d\'equivalence) 
qu'on noterait $X\prec Y$.

(iii) D\'emontrer que la relation $X\prec Y$ d\'efinie au dessus est une relation d'ordre sur l'ensemble des classes d'\'equivalences de $\sim$.
\end{quote}

\sq Que peut-on d\'eduire du r\'esultat pr\'ec\'edent \`a propos des classes d'\'equivalence
dans un tournoi~?

\end{exo}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
