\begin{exercice}[Titre={Organiser un tournoi fermé !},TitreSolution={Organiser un tournoi fermé !}]

Dans tout l'exercice, on considère un entier naturel non nul $n$ \textbf{pair}.

Sacha doit organiser une compétition avec $n$ participants qui sont numérotés de 1 à $n$.

\begin{definition}
Pour $i$ et $j$ des entiers naturels compris entre $1$ et $n$ et $i<j$, on définit et on note par le couple $(i,j)$ un \textbf{match} entre le participant $i$ et le participant $j$.
\end{definition}

Par exemple, pour $n=4$ participants, tous les matchs possibles sont $(1,2)$, $(1,3)$, $(1,4)$, $(2,3)$, $(2,4)$ et $(3,4)$.

On peut représenter ces six matchs sous la forme d'un tableau :

\begin{center}
	\begin{tabular}{|c|c|c|c|c|}
	\hline 
	$ $ &  $j=1$ & $j=2$ & $j=3$ & $j=4$ \\ 
	\hline 
	$ i=1$ &   \crosscell & $(1,2)$ & $(1,3)$ & $(1,4)$ \\ 
	\hline 
	$ i=2$ &   \crosscell & \crosscell & $(2,3)$ & $(2,4)$ \\ 
	\hline 
	$ i=3$ &   \crosscell & \crosscell & \crosscell & $(3,4)$ \\
	\hline 
	\end{tabular} 
\end{center}

\begin{enumerate}

\item Dans cette question, on considère une compétition avec $n=6$ participants.

 	\begin{enumerate}
	\item Compléter le tableau de l'\textbf{annexe} (\textbf{à rendre avec la copie}) afin de lister tous les matchs possibles. On barrera les cases inutiles de ce tableau.

	\item Combien a-t-on de matchs possibles pour $n=6$ participants ?
	\end{enumerate}

\item Dans cette question, on revient au cas général avec $n$ participants.

En remarquant que l'on représente les matchs à l'aide d'un tableau, constitué de $n$ colonnes et de $n-1$ lignes, dont on barre la moitié des cases, montrer que l'on a $\dfrac{n(n-1)}{2}$ matchs possibles au total.

\end{enumerate}


\begin{definition}
\begin{itemize}[label=\textbullet, leftmargin=*]
\item On appelle \textbf{série} un ensemble de $\dfrac{n}{2}$ matchs tel que tous les participants de la compétition jouent et ne jouent qu'un seul match.
\item On appelle \textbf{tournoi} la liste ordonnée des $n-1$ séries, que l'on numérote de 1 à $n-1$, telle que chaque participant n'affronte jamais deux fois un même adversaire.
\end{itemize}
\end{definition}

Voici un exemple de tournoi pour $n=4$ participants que l'on a représenté sous la forme d'un tableau :

\begin{center}
	\begin{tabular}{|c|c|c|}
	\hline 
	Série 1 &  $(1,2)$ & $(3,4)$ \\ 
	\hline 
	Série 2 &  $(1,3)$ & $(2,4)$ \\ 
	\hline 
	Série 3 &  $(1,4)$ & $(2,3)$ \\ 
	\hline 
	\end{tabular} 
\end{center}

On remarque alors que :
\begin{itemize}[label=\textbullet]
\item chaque participant n'affronte jamais deux fois le même adversaire ;
\item l'ordre des matchs dans une même série n'a pas d'importance.
\end{itemize}

\begin{enumerate}[start = 3]

\item Combien peut-on organiser de tournois différents avec $n=4$ participants ?

\item Compléter le tableau de l'\textbf{annexe} (\textbf{à rendre avec la copie}) pour obtenir un exemple de tournoi avec $n=6$ participants.

%\newpage
\item Dans cette question, on considère un tournoi avec $n=6$ participants. 

On notera par exemple $(1,5),(3,4),(2,6)$ une série.
\begin{enumerate}
	\item Combien a-t-on de séries possibles telles que les participants 1 et 2 se rencontrent ? Les citer.
	\item On suppose que la première série est la série $(1,2),(3,4),(5,6)$. Combien a-t-on alors de secondes séries possibles telles que les participants 1 et 3 s'affrontent ? On rappelle qu'un participant ne peut pas affronter deux fois le même adversaire.
	\item On suppose que la première série est $(1,2),(3,4),(5,6)$, que la seconde série est $(1,3),(2,6),(4,5)$ et qu'à la troisième série les participants 1 et 4 se rencontrent. Démontrer qu'il n'y a qu'une seule troisième série possible que l'on donnera.
	\item En déduire un exemple de tournoi où à la série n°$i$, le participant 1 rencontre le participant $i+1$, on complètera le tableau correspondant de l'\textbf{annexe} (\textbf{à rendre avec la copie}) .
	\item Combien a-t-on de tournois possibles où à la série n°$i$, le participant 1 rencontre le participant $i+1$ ?
	\item Combien peut-on organiser de tournois différents ?
	\end{enumerate}

\item On considère l'algorithme suivant afin de construire un tournoi avec $n$ participants. \\
Soit le match $(i,j)$ avec $1\leqslant i<j\leqslant n$ :
\begin{itemize}[label=\textbullet]
	\item Si $j<n$ et $i+j-1<n$ alors les participants $i$ et $j$ s'affronteront à la série $i+j-1$.
	\item Si $j<n$ et $i+j-1\geqslant n$ alors les participants $i$ et $j$ s'affronteront à la série $i+j-n$.
	\item Si $j=n$ et $2i \leqslant n$ alors les participants $i$ et $j$ s'affronteront à la ronde $2i-1$.
	\item Si $j=n$ et $2i>n$ alors les participants $i$ et $j$ s'affronteront à la ronde $2i-n$.
\end{itemize}
Compléter le tableau de l'\textbf{annexe} (\textbf{à rendre avec la copie}) correspondant au tournoi obtenu à l'aide de cet algorithme pour $n=6$ participants.

\end{enumerate}
\newpage 
\begin{center}
Annexe
\end{center}
\subsection*{Question 1.(a)}


\begin{center}
    % Fixation de la largeur totale du tableau
    \setlength{\tabcolsep}{5pt} % Espacement horizontal à l'intérieur des cellules
    \renewcommand{\arraystretch}{1.5} % Espacement vertical entre les lignes

    % Création du tableau avec colonnes égales
    \begin{tabularx}{0.8\linewidth}{|*{7}{>{\centering\arraybackslash}X|}} % 7 colonnes égales
    \hline 
    % Ligne d'en-tête
         & $j=1$ &  &  &  &  &  \\ 
    \hline 
    % Contenu du tableau
    $i=1$ & \crosscell &  &  &  &  &  \\ 
    \hline 
     &  &  &  &  &  &  \\ 
    \hline 
    &  &  & &  &  &  \\ 
    \hline 
     &  &  &  & &  &  \\ 
    \hline
     &  &  &  &  &  &  \\ 
    \hline 
    \end{tabularx}
\end{center}

\subsection*{Question 4}

\begin{center}
    % Fixation de la largeur totale du tableau
    \setlength{\tabcolsep}{5pt} % Espacement horizontal à l'intérieur des cellules
    \renewcommand{\arraystretch}{1.5} % Espacement vertical entre les lignes

    % Création du tableau avec colonnes égales
    \begin{tabularx}{0.7\linewidth}{|*{4}{>{\centering\arraybackslash}X|}} % 4 colonnes égales
    	\hline
    	Série 1 & $(1,2)$ & $(3,4)$ &    \\ 
    	\hline
	Série 2 & $(1,3)$ & $(2,5)$ &    \\ 
    	\hline
	Série 3 & $(1,4)$ &  &    \\ 
    	\hline 
	Série 4 & $(1,5)$ &  &    \\ 
    	\hline 
	Série 5 & $(1,6)$ &  &    \\ 
    	\hline 
    
    \end{tabularx}
\end{center}

\subsection*{Question 5.(d)}

\begin{center}
    % Fixation de la largeur totale du tableau
    \setlength{\tabcolsep}{5pt} % Espacement horizontal à l'intérieur des cellules
    \renewcommand{\arraystretch}{1.5} % Espacement vertical entre les lignes

    % Création du tableau avec colonnes égales
    \begin{tabularx}{0.7\linewidth}{|*{4}{>{\centering\arraybackslash}X|}} % 4 colonnes égales
    	\hline
    	Série 1 & $(1,2)$ & $(3,4)$ &    \\ 
    	\hline
	Série 2 & $(1,3)$ & $(2,6)$ &    \\ 
    	\hline
	Série 3 &  &  &    \\ 
    	\hline 
	Série 4 &  &  &    \\ 
    	\hline 
	Série 5 &  &  &    \\ 
    	\hline 
    
    \end{tabularx}
\end{center}

\subsection*{Question 6}

\begin{center}
    % Fixation de la largeur totale du tableau
    \setlength{\tabcolsep}{5pt} % Espacement horizontal à l'intérieur des cellules
    \renewcommand{\arraystretch}{1.5} % Espacement vertical entre les lignes

    % Création du tableau avec colonnes égales
    \begin{tabularx}{0.7\linewidth}{|*{4}{>{\centering\arraybackslash}X|}} % 4 colonnes égales
    	\hline
    	Série 1 &  &  &    \\ 
    	\hline
	Série 2 &  &  &    \\ 
    	\hline
	Série 3 &  &  &    \\ 
    	\hline 
	Série 4 &  &  &    \\ 
    	\hline 
	Série 5 &  &  &    \\ 
    	\hline 
    
    \end{tabularx}
\end{center}
\end{exercice}

\begin{Solution}

\begin{enumerate}

\item Dans cette question, on considère une compétition avec $n=6$ participants.

 	\begin{enumerate}
	\item 
	\begin{center}
    % Fixation de la largeur totale du tableau
    \setlength{\tabcolsep}{5pt} % Espacement horizontal à l'intérieur des cellules
    \renewcommand{\arraystretch}{1.5} % Espacement vertical entre les lignes
    % Création du tableau avec colonnes égales
    \begin{tabularx}{0.8\linewidth}{|*{7}{>{\centering\arraybackslash}X|}} % 7 colonnes égales
    \hline 
    % Ligne d'en-tête
         & $j=1$ & $j=2$  & $j=3$ & $j=4$  &  $j=5$ & $j=6$   \\ 
    \hline 
    % Contenu du tableau
    $i=1$ & \crosscell &  $(1,2)$ &  $(1,3)$ & $(1,4)$ & $(1,5)$ & $(1,6)$  \\ 
    \hline 
     $i=2$ &  \crosscell &  \crosscell & $(2,3)$ & $(2,4)$ & $(2,5)$ & $(2,6)$  \\ 
    \hline 
    $i=3$ &  \crosscell &  \crosscell & \crosscell & $(3,4)$ & $(3,5)$ & $(3,6)$  \\ 
    \hline 
     $i=4$ &  \crosscell &  \crosscell & \crosscell & \crosscell & $(4,5)$ & $(4,6)$ \\ 
    \hline
     $i=5$ &  \crosscell &  \crosscell& \crosscell & \crosscell & \crosscell &  $(5,6)$\\ 
    \hline 
    \end{tabularx}
\end{center}

	\item On a donc 15 matchs possibles pour $n=6$ participants.\\
	(1,2), (1,3), (1,4), (1,5), (1,6), (2,3), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6), (4,5), (4,6), (5,6)
	\end{enumerate}

\item On a $n \times (n-1)$ cases dans un tableau de $n$ colonnes et de $n-1$ lignes.
Comme on barre la moitié des cases d'un tel tableau, il reste $\dfrac{n(n-1)}{2}$ cases non barrées qui correspondent aux matchs possibles.
On a donc $\dfrac{n(n-1)}{2}$ matchs possibles. 

\item Une série est déterminée par le choix de l'adversaire du participant 1.\\ On a donc 3 séries possibles. On a 3 choix pour la première série, 2 pour la seconde, et 1 pour la dernière.\\ On a donc $3\times2=6$ tournois possibles.

\item 
\begin{center}
    % Fixation de la largeur totale du tableau
    \setlength{\tabcolsep}{5pt} % Espacement horizontal à l'intérieur des cellules
    \renewcommand{\arraystretch}{1.5} % Espacement vertical entre les lignes
    % Création du tableau avec colonnes égales
    \begin{tabularx}{0.7\linewidth}{|*{4}{>{\centering\arraybackslash}X|}} % 4 colonnes égales
    	\hline
    	Série 1 & $(1,2)$ & $(3,4)$ &  $(5,6)$  \\ 
    	\hline
	Série 2 & $(1,3)$ & $(2,5)$ &  $(4,6)$  \\ 
    	\hline
	Série 3 & $(1,4)$ & $(2,6)$  & $(3,5)$   \\ 
    	\hline 
	Série 4 & $(1,5)$ & $(2,4)$  & $(3,6)$   \\ 
    	\hline 
	Série 5 & $(1,6)$ & $(2,3)$ & $(4,5)$   \\ 
    	\hline     
    \end{tabularx}
\end{center}

\item Dans cette question, on considère un tournoi avec $n=6$ participants. 
\begin{enumerate}
	\item On peut en construire trois, cela dépend de l'adversaire du participant 3 qui a trois possibilités parmi les participants 4, 5 et 6 :
\begin{itemize}[label=\textbullet]
\item $(1,2),(3,4),(5,6)$
\item $(1,2),(3,5),(4,6)$
\item $(1,2),(3,6),(4,5)$
\end{itemize}

	\item On considère l'adversaire du participant 2 à la seconde série :
\begin{itemize}[label=\textbullet]
\item Si c'est le participant 4, alors les participants 5 et 6 doivent s'affronter, ce qui n'est pas possible car ils se sont déjà affrontés ;
\item Si c'est le participant 5, on obtient comme seconde série $(1,3),(2,5),(4,6)$ ;
\item Si c'est le participant 6, on obtient comme seconde série $(1,3), (2,6), (4,5)$.
\end{itemize}
Ainsi on a deux secondes séries possibles.

	\item On considère l'adversaire du participant 2 à la seconde série :
\begin{itemize}[label=\textbullet]
	\item Si c'est le participant 3, alors les participants 5 et 6 doivent s'affronter, ce qui n'est pas possible car ils se sont déjà affrontés ;
	\item Si c'est le participant 5, on obtient comme troisième série $(1,4),(2,5),(3,6)$ ;
	\item Cela ne peut pas être le participant 6 car les participants 2 et 6 se sont déjà rencontrés.
\end{itemize}
Ainsi on a une seule troisième série possible : $(1,4), (2,5), (3,6)$.

	\item 
\begin{center}
    % Fixation de la largeur totale du tableau
    \setlength{\tabcolsep}{5pt} % Espacement horizontal à l'intérieur des cellules
    \renewcommand{\arraystretch}{1.5} % Espacement vertical entre les lignes
    % Création du tableau avec colonnes égales
    \begin{tabularx}{0.7\linewidth}{|*{4}{>{\centering\arraybackslash}X|}} % 4 colonnes égales
    	\hline
    	Série 1 & $(1,2)$ & $(3,4)$ & $(5,6)$    \\ 
    	\hline
	Série 2 & $(1,3)$ & $(2,6)$ &  $(4,5)$  \\ 
    	\hline
	Série 3 & $(1,4)$ & $(2,5)$ & $(3,6)$   \\ 
    	\hline 
	Série 4 & $(1,5)$  & $(2,3)$ & $(4,6)$   \\ 
    	\hline 
	Série 5 & $(1,6)$ & $(2,4)$ & $(3,5)$   \\ 
    	\hline     
    \end{tabularx}
\end{center}

	\item On remarque qu'en fixant la condition qu'à la série n°$i$, le participant $1$ rencontre le participant $i+1$, on a trois choix pour la première série, puis deux choix pour la seconde série, les autres séries étant définies de manière unique.\\
Ainsi on a $3\times 2=6$ tels tournois possibles.

	\item On obtient un tournoi par permutation des séries d'un des tournois de la question précédente. C'est-à dire que pour un tournoi donné de la question précédente, on peut obtenir $5\times 4\times3\times2=120$ tournois.
En effet, on a :
\begin{itemize}[label=\textbullet]
	\item Cinq choix pour le numéro de la série contenant le match $(1,2)$ ;
	\item  Quatre choix pour le numéro de la série contenant le match $(1,3)$ ;
	\item Trois choix pour le numéro de la série contenant le match $(1,4)$ ;
	\item Deux choix pour le numéro de la série contenant le match $(1,5)$ ;
	\item Un choix pour le numéro de la série contenant le match $(1,5)$.
\end{itemize}
Comme on a 6 tournois de la forme de la question précédente, on en déduit que l'on peut organiser $6\times 120=720$ tournois possibles.
	\end{enumerate}

\item 
\begin{center}
    % Fixation de la largeur totale du tableau
    \setlength{\tabcolsep}{5pt} % Espacement horizontal à l'intérieur des cellules
    \renewcommand{\arraystretch}{1.5} % Espacement vertical entre les lignes
    % Création du tableau avec colonnes égales
    \begin{tabularx}{0.7\linewidth}{|*{4}{>{\centering\arraybackslash}X|}} % 4 colonnes égales
    	\hline
    	Série 1 & $(1,6)$ & $(2,5)$  &  $(3,4)$  \\ 
    	\hline
	Série 2 & $(1,2)$ & $(3,5)$ & $(4,6)$   \\ 
    	\hline
	Série 3 & $(1,3)$ & $(2,6)$ & $(4,5)$   \\ 
    	\hline 
	Série 4 & $(1,4)$ & $(2,3)$ & $(5,6)$   \\ 
    	\hline 
	Série 5 & $(1,5)$  & $(2,4)$  &  $(3,6)$  \\     	\hline     
    \end{tabularx}
\end{center}

\end{enumerate}

\end{Solution}