\documentclass[documents]{monexamen}
%\documentclass[documents]{monexamen}
%\setlength{\parindent}{0pt}

\usepackage{graphicx}
\usepackage{a4wide,amssymb,frenchle}
\usepackage[latin1]{inputenc} %% entr\'ee 8 bits iso-latin1
\usepackage[T1]{fontenc}      %% encodage 8 bits des fontes utilis\'ees

\newcommand{\f}{\ensuremath{\uparrow}}


\newcommand{\f}{\ensuremath{\uparrow}}


\begin{document}

\entete{Polytech' Nice Sophia}
{ }{05}{06}{Math\'{e}matiques  Discr\`{e}tes\\ du 27 Septembre 2005}{Dur\'{e}e : 60  minutes}% \
%{Probabilit\'{e}s}{02}{03}{du 1er Avril  2003 }
\\
\addtolength{\evensidemargin}{-1cm}
\addtolength{\oddsidemargin}{-1cm}
\reversemarginpar{ 

\begin{tabular}{l|l}
1 &  \ \  \\\hline
2 &   \\\hline
3 &   \\\hline
4 &   \\\hline
5 &   \\\hline
6 &   \\\hline
7 &   \\

\end{tabular}
}
\\

Toutes vos r\'{e}ponses doivent \^{e}tre justifi\'{e}es par une d\'{e}monstration ou un contre-exemple.

Aucun document autorisé

\section {R\'{e}currence simple}
Montrer que 
\[: \sum _{i=1}^{n}\frac 1{i^2}< 2 \]
(Indication : montrer la propriété en remplaçant $2$ par $2-\frac{1}{n}$ dans le terme de droite.)

Montrons par récurrence sur $n$ que $\sum _{i=1}^{n}\frac 1{i^2}\leq 2- \frac {1}{n} $
\begin{itemize}
  \item Base $n$=1 ,  $\sum _{i=1}^1\frac 1{i^2}=1 \leq  2-\frac{1}{1} $
  \item Supposons que l'on ait $\sum _{i=1}^{n}\frac 1{i^2}\leq  2-\frac{1}{n}$, alors
  $\sum _{i=1}^{n+1}\frac 1{i^2}=\sum _{i=1}^n\frac 1{i^2}+ \frac{1}{{(n+1)}^2}\leq 2-\frac{1}{n} +\frac{1}{{(n+1)}^2}$
  Or $\frac{1}{n} -\frac{1}{{n+1}^2}> \frac{1}{n+1}$ , donc on a bien
  $\sum _{i=1}^{n+1}\frac 1{i^2} \leq 2- \frac{1}{n+1}$
\end{itemize}
 Le résultat demandé en découle puisque $2-\frac {1}{n} <2$, pour tout $n$ entier.

\section {Plus petit élément}
Démontrer que toute partie finie non vide d'un ensemble totalement ordonné contient un plus petit élément.

Montrons que toute partie $F$ de cardinal $k>0 $ d'un ensemble totalement ordonné$(E, \leq )$  contient un plus petit élément, par récurrence sur $k$.

\begin{itemize}
\item $k=1$ L'unique élément de $E'$ est le plus petit élément de $E'$, puis qu'il est inférieur ou égal à lui même.
\item Supposons le résultat vrai pour toute partie $F$ de $E$ de cardinal $k$. Soit $F'$ une partie de $E$ de cardinal $k+1$.
Soit $u$ un élément quelconque de $F'$. Considérons $F"=F'-\{u\}$. $F"$ étant de cardinal $k$, il admet un plus petit élément $m$. Si $m \leq u$, alors $m$ est un plus petit élément de $F'$, sinon, on sait que $u<m$ et $u$ est donc le plus petit élément de $F'$.
\end{itemize}


\section {Division}
On considère sur IN, la relation {\em divise} notée $|$ définie par $a | b$ si il existe un entier $k$ tel que $b = ka$ . \\
Montrer que $|$ est une relation d'ordre.\\
Est-ce un ordre total ?\\
Donner s'ils existent le plus petit et le plus grand élément de IN pour $|$.


C'est une relation d'ordre partiel .

En effet la relation est :
\begin{itemize}
\item reflexive puisque pour tout entier $n$, on a $n|n$
\item transitive: si $n|m$ et $m|q$, alors $n|q$
\item antisymétrique : si $n|m$ et $m|n$, alors $n\leq m$ et $m \leq n$  (pour la relation d'ordre usuelle) et donc $n=m$
\end{itemize}
L'ordre est partiel puisque l'on n'a ni $2|5$, ni $5|2$.

Quelque soit $k$ entier, on a $1|k$ et $k|0$, donc $1$ est le minimum de IN pour la relation $|$ tandis ue $0$ est le maximum 
\section {Ordre ?}
Donner la définition d'une relation d'ordre et donner un exemple de relation d'ordre (différent de ceux vus en cours/TD).

Un ordre est une relation binaire, reflexive, antisymmétrique et transitive.
Comme exemple de relation d'ordre non vue en cours , on peut par exemple choisir sur l'ensemble des mots sur un alphabet A, la relation mRm' si et seulement si m est un sous mot de m' (par exemple bra R abracadabra)

\section {Ordre strict?}
Sur l'ensemble des cyclistes professionnels, on considère la relation {\em est meilleur que} définie par {$x$ est meilleur que $y$} si $x$ est arrivé devant $y$ à toutes les courses de l'UCI pro-tour où l'un et l'autre ont couru, autrement dit dès que $x$ et $y$ courent ensemble $x$ arrive devant $y$.\\ Il n'y a aucun ex eaquo dans le système de classement UCI.
Est-ce une relation d'ordre  strict ? \\
Même question si l'on suppose en outre que tous les coureurs participent à toutes les courses.


Si l'on ne suppose pas que tous les coureurs participent à toutes les courses, on peut etre dans le cas ou $x$ est arrivé avant $y$ dans la seule course qu'ils ont tous les deux couru, tandis que $y$ et $z$ n'ont couru ensemble que sur une autre course lors de la quelle $y$  est arrivé avant $z$ . Il est alors tout a fait possible que $x$ et $z$ n'aient jamais couru ensemble, ou bien qu'ils aient couru ensemble lors d'une troisième course où $z$ est arrivé avant $x$.

La relation n'est donc pas transitive. En revanche elle est antisymétrique (puisqu'il n'y a jamais d'ex aequo) et antiréflexive (nul n'arrive avant lui même)

En revanche si tous les coureurs ont participé à toutes les courses, la relation devient transitive, et il s'agit donc d'un ordre strict. Cet ordre strict est aussi partiel, puisque sauf s'il n'y a qu'une course, il est possible que $x$ et $y$ ne soient pas toujours classés dans le même ordre.




\section {Ordre d'ainesse}
On considère $E$ l'ensemble des SI1 et des MAM1.Soient $a$ et $b$ deux éléments de $E$, on dit que $a R b$ si et seulement si $a$  n'est pas né plus tard que  $b$.  La relation $R$ est elle un ordre ? Pour chacune des propriétés d'une relation d'ordre dire si $R$ vérifie la propriété. Si $R$ est une relation d'ordre est ce un ordre total ou partiel ? 

La relation est reflexive (nul n'est né après lui même) elle est transitive, mais elle est antisymétrique seulement si il n'y a pas deux personnes dans $E$ qui soient nés exactement en même temps. Dans ce cas particulier là, c'est un ordre total.


\section {Calculateur prodige (d'après un problème du journal {\em Le Monde}}
Un magicien demande à un spectateur de choisir 2 nombres, et de les écrire sur une feuille l'un en dessous de l'autre, puis d'en faire la somme et de l'écrire en dessous du dernier nombre écrit, puis de faire la somme du nombre obtenu et du nombre précédent et de l'écrire en dessous du dernier nombre écrit, puis de recommencer autant de fois qu'il veut. Le magicien lui demande ensuite le premier nombre choisi ainsi que les 2 derniers nombres qu'il a écrit, et après invocation d'une formule magique (!), lui donne la somme de tous les nombres que le spectateur a écrit. Quelle est la formule magique du magicien ?




\end{document}