\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}}


\begin{document}

\entete{Polytech' Nice Sophia}
{ }{05}{06}{Mathématiques  Discrètes\\ du 19 Octobre 2005}{Duré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 &   \\

\end{tabular}
}
\\

Toutes vos r\'{e}ponses doivent \^{e}tre justifi\'{e}es par une d\'{e}monstration ou un contre-exemple.
Si vous pensez que le texte d'une question est ambigu (voire erroné)  faites une hypothèse raisonnable et écrivez la sur votre copie.

Aucun document autorisé

\section {R\'{e}currence simple [2 points]}
Montrer par récurrence que pour tout $n$ entier 
la somme des $n$ premiers entiers multiples de cinq et impairs est egal à $5n^2$
\begin{copie}
  \lignes{15}
\end{copie}


\section {Des petits, des grands? [3 points]}
On considère l'ensemble des parties de N ordonné par l'inclusion.
Soit $A = \{ \{1,2\},\{1,5\},\{1,4\}\}$ et soit $B=\{ \{1,2\},\{1,2,3\},\{1\},\{1,4\},\{1,4,3\} \}$
\begin{itemize}
\item $A$ et $B$ ont ils un ou des  minorants ? si oui lesquels, si non pourquoi?
\item $A$ et $B$ ont ils un ou des  éléments minimaux ? si oui lesquels, si non pourquoi?
\item $A$ et $B$ ont ils un ou des plus petits éléments ? si oui lesquels, si non pourquoi?
\item $A$ et $B$ ont ils un ou des  majorants ? si oui lesquels, si non pourquoi?
\item $A$ et $B$ ont ils un ou des éléments maximaux ? si oui lesquels, si non pourquoi?
\item $A$ et $B$ ont ils un ou des plus grands éléments ? si oui lesquels, si non pourquoi?
\end{itemize}

\begin{copie}
  \lignes{27}
\end{copie}

\section {Ordre bien fondé [5 points]}
Montrer que si un ensemble est ordonné par une relation d'ordre total bien fondé (c'est à dire un bon ordre), toute partie  non vide admet un plus petit élément.\\
Est-ce que la propriété est toujours vraie même si l'ordre n'est pas total (si oui prouver, si non donner un contre-exemple) ?\\
Est-ce que la propriété est toujours vraie même si l'ordre n'est pas bien fondé (si oui prouver, si non donner un contre-exemple) ?
\begin{copie}
  \lignes{29}
\end{copie}

\section {Définition inductive [3 points]}

On considère l'ensemble $E$ défini de manière inductive par
\begin{itemize}
\item Base : $\epsilon \in E$
\item Règles :
\begin{itemize}
\item Si $ m \in E$ alors $10m0 \in E$
\item Si $ m \in E$ alors $01m0 \in E$
\item Si $ m \in E$ alors $00m1 \in E$
\end{itemize}
\end{itemize}
Soit $M$ le sous-ensemble de $\{0,1\}^*$ formé des mots ayant deux fois plus  de 0 que de 1.
\begin{enumerate}
\item A-t-on $M$ inclus dans $E$?
\item A-t-on $E$ inclus dans $M$?
\item Le schéma définissant $E$ est-il  libre?
\end{enumerate}

\begin{copie}
  \lignes{25}
\end{copie}

\section{Ordre inductif [4 points]}
Donner et prouvez un schéma inductif pour $M=\{ (m,n,p)\in N^3 , m \leq n \leq p \}$
\begin{copie}
  \lignes{30}
\end{copie}

\section{Maximal  [3 points]}
Montrer que pour un ordre  quelconque (total ou partiel), toute partie finie non vide admet au moins un élément maximal.
\begin{copie}
  \lignes{32}
\end{copie}





\end{document}