\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ématiques  Discrètes\\ du 12 Octobre 2005}{Durée : 1 heure}
\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.

Aucun document autorisé

\section {R\'{e}currence simple}
Montrer par récurrence que pour tout n entier strictement positif
la somme des $n$ premiers entiers multiples de trois et impairs est egal à $3n^2$

\begin{itemize}
\item Base n=1 , le premier entier impair multiple de 3 est 3, et on a bien $3=3.1^2$
\item On suppose que $\sum _0 ^{n-1} 6k+3=3n^2$.
\item On a alors $\sum _0 ^{n} 6k+3=3n^2+6n+3=3(n+1)^2$.
\end {itemize}

\section {Des petits , des grands? }
On considère l'ensemble des parties de N ordonné par l'inclusion.
Soit $A = \{ \{a,b\},\{a,b,d\},\{a,d\}\}$ et soit $B=\{ \{a,b\},\{a,b,c\},\{a\}\}$
\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 plus petits éléments ? si oui lesquels, si non pourquoi?
\item $A$ et $B$ ont ils un ou des plus éléments minimaux ? 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 plus grands éléments ? si oui lesquels, si non pourquoi?
\item $A$ et $B$ ont ils un ou des plus éléments maximaux ? si oui lesquels, si non pourquoi?
\end{itemize}

\begin{itemize}
\item L'ensemble des minorants de $A$ =$\{ \emptyset, \{a\}\}$ 
\item L'ensemble des minorants de $B$ =$\{ \emptyset, \{a\}\}$ 
\item $A$ n' a pas de plus petit élément puisqu'aucun de ses minorants ne lui appartient, tandis que $B$ a $\{a\}$ comme plus petit élément.
\item L'ensemble des éléments minimaux  de $A$ =$\{ \{a,b\}, \{a,d\}\}$ 
\item L'ensemble des éléments minimaux  de $B$ =$\{ \{a\}\}$ 
\item L'ensemble des majorants de $A$ =$\{ E \subset N /  \{a,b,d\} \subset E\}$ 
\item L'ensemble des majorants de $B$ =$\{ E \subset N /  \{a,b,c\} \subset E\}$ 
\item Le plus grand élément de $A$ est $\{a,b,d\}$, tandis que le plus grand élément de $B$ est $\{a,b,c\}$
\item  $\{a,b,d\}$ est l'unique élément maximal de $A$ et $\{a,b,c\}$ est l'unique élément maximal de $B$.
\end{itemize}

\section { Ordre bien fondé}
Une relation d'ordre est telle que pour tout élément $x$, il existe un nombre fini d'éléments inférieurs à $x$, cette relation est elle bien fondée ? La réciproque est elle vraie?

Oui si l'on considére une suite strictement décroissante, son nombre de termes est borné par le nombre d'éléments (fini) qui sont inférieurs à son premier terme
La réciproque est fausse, on en a vu des exemples en cours , par exemple l'ordre lexicographique sur $NxN$ est bien fondé, mais tous les couples de la forme $(1,n)$ sont plus petits que $2,1)$.
\section {Définition inductive}

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 $10m \in E$
\item Si $ m \in E$ alors $01m \in E$
\item Si $ m \in E$ alors $m10 \in E$
\item Si $ m \in E$ alors $m01 \in E$
\end{itemize}
\end{itemize}

Soit $M$ le sous-ensemble de $\{0,1\}^*$ formé des mots ayant autant de 0 que de 1.
\begin{enumerate}
\item A-t-on $M$ inclus dans $E$?
\item A-t-on $E$ inclus dans $M$?
\item Montrer que le schéma définissant $E$ n'est pas libre
\item Modifier le schéma pour le rendre libre (sans modifier l'ensemble $E$ obtenu, bien sûr)
\item Donner (sans preuve ) un schéma inductif pour $M$ 

\end{enumerate}


\begin{enumerate}
	\item  $M$ n'est pas inclus dans $E$, car 1100 est dans $M$ mais pas dans $E$
	\item  $E$ est inclus dans $M$. Il suffit d'utiliser l'induction structurelle et de montrer
	\begin{itemize}
		\item $\epsilon \in M$
		\item Si $ m \in M$ alors $10m \in M$
		\item Si $ m \in M$ alors $01m \in M$
		\item Si $ m \in M$ alors $m10 \in M$
		\item Si $ m \in M$ alors $m01 \in M$
		\end{itemize}
	\item Le schéma définissant $E$ n'est pas libre, car le mot $1010$ peut être construit par la règle 1 ou la règle 3.
	\item Si l'on conserve uniquement les deux premieres règles on obtient un schéma libre pour le même ensemble:

		Soit $F$ défini par
	\begin{itemize}
		\item $\epsilon \in F$
		\item Si $ m \in F$ alors $10m \in F$
		\item Si $ m \in F$ alors $01m \in F$
	\end{itemize}

	Le schéma définissant $F$ est libre car
	\begin{itemize}
		\item $\epsilon$ ne peut être produit par aucune des deux règles
		\item $\forall m, m' \in F$, $10m \neq 01m'$
		\item $\forall m, m' \in F$, $10m = 10m'\Rightarrow m=m'$
		\item $\forall m, m' \in F$, $01m = 01m'\Rightarrow m=m'$
	\end{itemize}

	Clairement $F \subset E$.
	 
	Montrons $E \subset F$ par induction structurelle sur E
	\begin{itemize}
		\item $\epsilon$ appartient à $F$
		\item Si $ m \in  F$, alors $10m \in F$ : évident 
		\item Si $ m \in  F$, alors $01m \in F$ : évident
		\item P(m) : Si $ m \in  F$, alors $m10 \in F$ : pas évident !
   
  	 mais on va le montrer par induction structurelle sur $F$
   	\begin{itemize}
			\item Pour $m=\epsilon$ on a bien $10 \in F$, donc $P(\epsilon )$ est vraie
			\item Supposons $P(m)$ et montrons $P(10m)$.
    	Soit $10m$ dans $F$. Puisque le schéma définissant $F$ est libre, $10m$ a été construit à partir de $m$ et de la règle 1 et donc $m$ est dans $F$. Mais alors puisque P(m) est vrai, $m10 \in F$. Par définition de $F$, on sait que $10m10$ est alors dans $F$. On a donc bien $P(10m)$ vrai
    
			\item Supposons $P(m)$ et montrons $P(01m)$.
			
Soit $01m$ dans $F$. Puisque le schéma définissant $F$ est libre, $01m$ a été construit à partir de $m$ et de la règle 2 et donc $m$ est dans $F$. Mais alors puisque P(m) est vrai, $m10 \in F$. Par définition de $F$, on sait que $01m10$ est alors dans $F$. On a donc bien $P(01m)$ vrai

			\end{itemize}
   
		\item Si $ m \in  F$, alors $01m \in F$ :  se montre exactement comme l'implication précédente
	\end{itemize}
On a donc bien $E=F$, et l'on a donc trouvé un schéma libre définissant $E$
\item Un schéma possible pour $M$
\begin{itemize}
\item $\epsilon$ appartient à $M$
\item $m, m'  \in M \rightarrow Om1m'\in M$
\item $m, m'  \in M \rightarrow 1m0m'\in M$

\end{itemize}

\end{enumerate}
\section{Plus petit que}
Donner et prouvez un schéma inductif pour $P= \{ (m,n)\in N^2 , m \leq n\}$
\begin{itemize}
  \item Base $\{0,0\} \in S$
  \item $\{(p,q)\in S \Rightarrow (p+1,q+1) \in S$
  \item $\{(p,q)\in S \Rightarrow (p,q+1) \in S$
\end{itemize}

Montrons $P=S$
\begin{itemize}
	\item  $S \subset P$ se montre facilement par induction structurelle sur $S$, il suffit de vérifier que 
	\begin{itemize}
  	\item Base $0 \leq 0$
  	\item $p \leq q \Rightarrow p+1 \leq q+1 $
  	\item $p \leq q \Rightarrow p \leq q+1$
	\end{itemize}
	\item $P \subset S$
On va montrer par récurrence sur k, la propriété

$P(k) = \forall (m,n) \in N,   m+n \neq k, m \leq n $, on a $(m,n) \in S$
	\begin{itemize}
		\item Base k=0, P(0) est vraie car $(0,0) \in S$
		\item On suppose P(k) vraie.
		
Soit un couple $(m,n) \in N,  m+n \neq k+1, m \leq n$. 

Le seul cas à considérer est le cas où $m+n=k+1$.
			\begin{itemize}

			\item Si n=m , alors le couple $(m-1,n-1)$ est un couple d'entiers (on ne peut pas avoir $m=n=0$ et $m+n=k+1$ ) qui vérifie $m+n-2 <k$ et donc par hypothèse de récurrence  c'est un couple de $S$, par définition de $S$, le couple $(m,n)$ est lui aussi dans $S$ .
			\item
Si $m<n$, alors $m \leq n-1$, $(m,n-1)$ est un couple d'entiers ($n$ ne peut pas etre nul puisque $m<n$) et $m+n-1 \leq k$. Donc par hypothèse de récurrence c'est un couple de $S$, par définition de $S$, le couple $(m,n)$ est lui aussi dans $S$ .
		\end{itemize}
	\end{itemize}
	\end{itemize}
	
	Bien sur d'autres schémas sont possibles. 
\section{Maximal unique}
Montrer que pour un ordre  quelconque (total ou partiel), toute partie finie admettant un unique élément maximal, admet un plus grand élément.

Démontrons par récurrence sur $k$ la propriété
$P(k)$ :toute partie finie de cardinal $k$ admettant un unique élément maximal, admet un plus grand élément

\begin{itemize}
\item $n=1$,  l'unique élément est à la fois maximal et plus grand élément de l'ensemble
\item Supposons $P(n)$ vrai, pour $n \geq 1$. Soit $A$ une partie de cardinal $n+1$ admettant $uniqmaximalA$ comme unique élément maximal. 
Soit $x_0$ un élément de $A$, différent de $uniqmaximalA$. 

Considerons $A'=A-\{x_0\}$. 


$uniqmaximalA$ est maximal dans $A'$. 

Supposons que $A'$ admette un autre élément maximal, $autremaxA'$. 

Puisque $autremaxA'$ n'est pas maximal dans $A$, c'est que $autremaxA' < x_0$. 

D'autre part, aucun élément de $A'$ n'est plus grand que $autremaxA'$, donc aucun élément de $A$ n'est plus grand que $x_0$, et donc $x_0$ est aussi maximal dans $A$, contradiction.

$A'$ a donc un unique élément maximal, et par hypothèse de récurrence, $A'$ admet $uniqmaxA$ comme plus grand élément.

Comme $x_0$ n'est pas maximal dans $A$, il existe $M'$ dans $A$ et donc dans $A'$, tel que $x_0 < M'$, comme $uniqumaxA$ est le plus grand élément de $A'$, on a $M'< uniqmaxA$, et donc $x_0 < uniqmaxA$, et donc $uniqmaxA$ est le plus grand élément de $A$.
\end{itemize}



Remarque : la démonstration devient triviale, si l'on suppose que l'ordre est total.





\end{document}