\documentclass[documents]{examen}
%\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{\'{E}cole Sup\'{e}rieure en Sciences
Informatiques}
{ }{05}{06}{Math\'{e}matiques  Discr\`{e}tes\\ du 16 Novembre 2005}{Dur\'{e}e : 2 heures}% \
%{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}
}
\\

Tous documents autorisés.

Toutes vos réponses doivent être justifiées par une dé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.


\section {Encadrement  \small[2 points]}
Soit $(E, \leq)$ un ensemble ordonné. Soit $A$ une partie finie et non vide de $E$. Montrer que pour tout $x$ dans $A$, il existe $m$ et $M$ tels que $m$ est un élément minimal de $A$, $M$ est maximal dans $A$ et $ m \leq x \leq M$


\begin{solution}
La preuve peut se faire par induction sur $A$.
Si $A$ est de cardinal 1, $m=M=x$ conviennent.

Supposons le résultat vrai pour toute partie $A$ de cardinal $k$. Soit $B$ une partie de cardinal $k+1$. Soit $x$ dans $B$, et soit $y$ un élément de $B$ distinct de $x$.
Soit $A=B-\{y\}$. Par hypothèse de récurrence, il existe $m$ et $M$ tels que $m$ est un élément minimal de $B$, $M$ est maximal dans $B$ et $ m \leq x \leq M$.
Si $m$ n'est pas minimal dans $A$, c'est que $y<m$, et dans ce cas $y$ est minimal dans $A$ et $y \leq x$.
Si $M$ n'est pas maximal dans $A$, c'est que $M<y$, et dans ce cas $y$ est maximal dans $A$ et $x \leq y$.


Autre preuve possible :

On considère l'ensemble des majorants de $x$ qui appartiennent à A. Cet ensemble est non vide et fini. Donc il admet des éléments maximaux. Tous ces éléments sont aussi maximaux dans $A$ et peuvent donc être choisis pour $M$. L'autre partie se montre de même.

\end{solution}
\begin{copie}
\lignes{20}
\end{copie}


\section {Cyclistes  \small[2 points] }
\begin{enumerate}
\item 
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$ à la première course de l'UCI pro-tour où ils ont couru ensemble.\\ Il n'y a aucun ex eaquo dans le système de classement UCI.
Cette relation est elle symétrique, antisymétrique, transitive? \\

\item
On considère maintenant la relation {\em est meilleur que} définie par {$x$ est meilleur que $y$} si $x$ est arrivé devant $y$ au moins une fois.\\ 
Cette relation est elle symétrique, antisymétrique, transitive? \\
\end{enumerate}
\begin{solution}
\begin{enumerate}
\item
Ce n'est pas transitif, si $a$ et $b$ ont couru ensemble pour la première fois lors d'une course $C_1$ où $a$ est arrivé avant $b$, , $b$ et $c$ ont couru ensemble lors d'une course $C_2$ où $b$ est arrivé avant $c$ et $a$ et $c$ n'ont jamais couru ensemble, alors $a$ est meilleur que $b$, $b$ et meilleur que $c$ et $a$ n'est pas meilleur que $c$.

La relation n'est pas symétrique, si $x$ est meilleur que $y$ alors $y$ n'est pas meilleur que $x$.
La relation est antisymétrique si $x$ est meilleur que $y$ et $y$ meilleur que $x$ alors $x=y$ (rappelons que $a \Rightarrow  b$ est vrai dès que $a$ est faux)

\item
La relation n'est ni symétrique ( $x$ peut arriver toujours avant $y$) ni antisymétrique ($x$ et $y$ peuvent être arrivés dans un ordre différent lors de deux courses différentes), ni transitive (on peut imaginer que lors de toutes les courses  sauf une $x$ arrive avant $y$ qui arrive avant $z$, et lors de la dernière course $y$ arrive avant $z$ qui arrive avant $x$.
On a donc $z$ meilleur que $x$ (dernière course) $x$ meilleur que $y$ (autres courses), mais l'on a pas $z$ meilleur que $y$.

\end{enumerate}

\end {solution}
\begin{copie}
\lignes {25}
\end{copie}
\section {Des petits, des grands?  \small[3 points]}
On considère l'ensemble  N ordonné par la divisibilité, c'est à dire 
$x \leq y$ si et seulement si il existe $d$ dans N, tel que $y=dx$
Soit $A = \{ 6,3,9,81\}$ et soit $B$ le sous ensemble de N formé des entiers dont l'écriture en base dix se termine par un 5.
\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 é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 éléments maximaux ? si oui lesquels, si non pourquoi?


\end{itemize}






\begin{solution}

  \ 


$A$ a pour minorants 1 et 3 , et pour majorants tous les multiples de 162 (dont 0) .

Le plus petit élément de $A$ est $3$, $A$ n' a pas de plus grand élément.

$3$ est le seul élément minimal de $A$, les éléments maximaux sont $6$ et $81$
les minorants de $B$ sont $1$ et $5$, $5$ est le plus petit élément de $B$. C'est aussi l'unique élément minimal de $B$
$B$ a 0 pour seule majorant, pas de plus grand élément et pas d'élément maximal. 
\end{solution}

\begin{copie}
\lignes {18}
\end{copie}

\section {Fibonnacci \small[4 points] }
\begin{enumerate}
\item Soit $f_n$ la suite de Fibonnacci définie par $f_0=0$, $f_1=1$, $f_n=f_{n-1} + f_{n-2}$, pour tout $n$, $n \geq 2$. Montrez que $f_k$ est pair si et seulement si $k$ est un multliple de trois. 
\item Soient $a$ et $b$ deux constantes, on défini la suite $u_n$ par $u_0=a$, $u_1=b$, $u_n=u_{n-1} + u_{n-2}$ pour tout $n$, $n \geq 2$. Enoncez pour $u_n$ une propriété analogue à celle de la question précédente pour $f_n$ , dépendant des valeurs de $a$ et $b$
\item Montrer que pour tout $n$, $n\geq 1$, $u_n= b f_n +af_{n-1}$

\end{enumerate}
\begin{solution}
\begin{enumerate}
\item
On montre par récurrence sur $k$ que pour tout $i \leq k$, $f_i$ est pair si et seulement si i est un multiple de trois.

Pour $k=1$ le résultat est vrai.

On suppose le résultat vrai pour $k \geq 1$. Considérons $f_{k+1}$.

Si $k+1$ est un multiple de trois, alors ni $k$ ni $k-1$ n'est un multiple de trois et par hypothèse de récurrence, $f_k$ et $f_{k-1}$ sont tous les deux impairs et donc $f_{k+1}$ est pair.

Si $k+1$ n'est pas un multiple de trois, alors exactent l'un des deux entiers  $k$ et $k-1$ n'est un multiple de trois et par hypothèse de récurrence, l'un des deux nombres $f_k$ et $f_{k-1}$ est pair et l'autre est  impair et donc $f_{k+1}$ est impair.
\item Si $ a $ et $b$ sont tous les deux pairs, alors clairement la suite $u_n$ est composée d'entieres pairs. 

Si $a$ est pair et $b$ impair, $u_n$ est pair si et seulement si $n$ est un multiple de trois. 

Si $a$ est impair et $b$ pair, $u_n$ est pair si et seulement si $n$ est congru à un modulo trois. 

Si $a$ est impair et $b$ impair, $u_n$ est pair si et seulement si $n$ est congru à deux modulo trois. 

Les preuves se font exactement comme pour la première question.
\item
Pour $n=1$ on a bien $u_1=b f_1+af_0=b$.


Supposons le résultat vrai jusqu'au rang  $n$ .

On a $u_{n+1} = u_n + u_{n-1} = bf_n+af_{n-1}+bf_{n-1}+af_{n-2}=bf_{n+1}+af_{n}$, le résultat est donc vrai aussi au rang $n+1$.


\end{enumerate}
\end{solution}
\begin{copie}
\lignes {27}
\end{copie}
\section {Définitions inductives \small[4 points]}
Soit $UP$ le sous ensemble des mots binaires, composés des mots admettant un nombre pair de "1".
Donnez et prouvez un schéma inductif  (si possible libre) pour $UP$. 

Soit $P$ le sous ensemble des mots binaires, composés des mots admettant un nombre pair de "1" et de "0".
Donnez et prouvez un schéma inductif pour $P$. 
 

\begin{solution}
\begin {enumerate}
\item 
\begin{itemize}

Soit $E$ l'ensemble défini inductivement par 
\item Base : $\epsilon \in E$

Règles :

\item $m \in E \rightarrow 0m \in E$

\item $m \in E$ et $m \neq 0m', \rightarrow m0 \in E$

\item$m \in E \rightarrow 1m1 \in E$

\item 
 $E \subset UP$ 
Se montre facilement par induction structurelle : 

$\epsilon \in UP$, puisqu'il comporte zéro un.

Si $m$ comporte un nombre pair de un, il en est clairement de même de $0m$, $m0$  et $1m1$
\item $UP \subset E$ 
 Montrons par récurrence sur k que tout mot de  $P$ de longueur inférieure ou égale à $k$ appartient à $ E$ 

Pour $k$ = 0 c'est vrai.

Supposons l'hypothèse vraie au rang $k$ et soit $m$ un mot de $P$ de longueur $k+1$.
Si $m$ commence par $0$ alors il s'écrit $0m'$ et puisque $m$ comporte un nombre pair de $1$, il en est de même pour $m'$ et donc $m'$ appartient à $P$. Par hypothèse de récurrence $m'$ est donc dans $E$ et par définition de $E$, on a donc $m$ dans $E$.
 
 Sinon,  $m$ termine par $0$ alors il s'écrit $m'0$ et puisque $m$ comporte un nombre pair de un, il en est de même pour $m'$ et donc $m'$ appartient à $P$. De plus $m'$ ne commence pas par $0$. Par hypothèse de récurrence $m'$ est donc dans $E$ et par définition de $E$, on a donc $m$ dans $E$.
 
 Si $m$ ne commence pas par $0$ et ne termine pas par $0$, alors il comporte au moins deux lettres (il ne peut pas comporter un seul un) et sa première et sa dernière lettre sont toutes les deux des $1$. Il existe donc $m'$ tel que $m=1m'1$.  Puisque $m$ comporte un nombre pair de un, il en est de même pour $m'$ et donc $m'$ appartient à $P$. Par hypothèse de récurrence $m'$ est donc dans $E$ et par définition de $E$, on a donc $m$ dans $E$.

 \item  Ce schéma est libre, en effet, $\epsilon$ ne peut pas être le résultat d'une règle. D'autre part si un mot est le résultat de la première règle, il commence par un zero et ne peut etre obtenu par la seconde ou la troisième règle.  De même si un mot est obtenu par la seconde règle il termine par un zéro et ne peut pas être obtenu par la troisième rèble. Engin lorsque l'on connait la règle qui a produit le mot, on connait aussi l'antécédent.
 \end{itemize}
 \item 
 \begin{itemize}
\item 
Soit $E$ l'ensemble défini inductivement par 

Base : $\epsilon \in E$

Règles :

$m \in E \rightarrow 00m \in E$

$m \in E   \rightarrow m00 \in E$

$m \in E   \rightarrow m11 \in E$

$m \in E   \rightarrow 11m \in E$

$m \in E \rightarrow 1m1 \in E$

$m \in E \rightarrow 0m0 \in E$

$m \in E \rightarrow 01m01 \in E$

$m \in E \rightarrow 10m10 \in E$

\item 
 $E \subset P$ 
Se montre facilement par induction structurelle : 
\item $P \subset E$ 
$\epsilon \in P$, puisqu'il comporte zéro "1" et zéro "0".

Si $m$ comporte un nombre pair de "1" et de "0", il en est clairement de même de $00m$, $m00$ ,$11m$, $m11$,$0m0$ et $1m1$
\item Montrons par récurrence sur k que tout mot de  $P$ de longueur inférieure ou égale à $k$ appartient à $ E$ 

Pour $k$ = 0 c'est vrai.
Supposons l'hypothèse vraie au rang $k$ et soit $m$ un mot de $P$ de longueur $k+1$.
Si $m$ commence par 0 alors 
\begin{itemize}
\item
s'il termine par 0, il s'écrit $0m'0$ et  $m'$  appartient à $P$. Par hypothèse de récurrence $m'$ est donc dans $E$ et par définition de $E$, on a donc $m$ dans $E$.
\item sinon il termine par 1 et s'écrit $0m'1$. m' ne peut pas être vide, sa première lettre est soit 0 soit 1.


\begin{itemize}
\item
si m' commence par 0, alors  $m= 00m"1$ et  $m"1$  appartient à $P$. Par hypothèse de récurrence $m"1$ est donc dans $E$ et donc par définition de $E$ on a  $m$ dans $E$.
\item sinon $m=01m"1$, m" ne peut pas être vide, sa dernière lettre est soit 0 soit 1.
\begin{itemize}
\item
si m" termine par 0, alors  $m= 01p01$ et  $p$  appartient à $P$. Par hypothèse de récurrence $p$ est donc dans $E$ et donc par définition de $E$ on a  $m$ dans $E$.
\item sinon $m=01p11$, et $01p$appartient à $P$. Par hypothèse de récurrence $p$ est donc dans $E$ et donc par définition de $E$ on a  $m$ dans $E$.
\end{itemize} 

\end{itemize} 


\end{itemize} 
Le cas où $m$ commence par 1 se traite de manière analogue
 \end{itemize}

\end{enumerate}
\end{solution}
 
 \begin{copie}
 \lignes{30}
 \end{copie}
\section {Récurrence  \small[3 points]}
Soit $u_n$ une suite d'entiers relatifs, telle que pour tout $n$, $ \sum _{i=0}^n u_i^3 =  (\sum _{i=0}^n u_i)^2 $.

Montrez que pour tout entier $n$ , il existe $m$ dans $N$, tel que $ \sum _{i=0}^n u_i =\frac{m(m+1)}{2}$.
 

\begin{copie}
 \lignes {30}
 \end{copie}
\begin{solution}
Pour $n=0$, on a $u_0^3=u_0^2$, donc soit $u_0=0$ et $m=0$ convient, soit $u_0=1$ et $m=1$ convient.

Supposons le résultat vrai pour un entier $n$ fixé.
On a donc $ \sum _{i=0}^{n+1} u_i^3 =\sum _{i=0}^n u_i^3 +u_{n+1}^3 =  (\frac{m(m+1)}{2})^2+u_{n+1}^3= (\sum _{i=0}^{n+1} u_i)^2 = (\frac{m(m+1)}{2}+u_{n+1})^2$.

On a donc $u_{n+1}^3=m(m+1)u_{n+1}+u_{n+1}^2$.
Les solutions de cette équations, sont $u_{n+1}=0$, $u_{n+1}=m+1$, et $u_{n+1}=-m$. Dans le premier cas, $\sum _{i=0}^{n+1} u_i =\frac{m(m+1)}{2} $, dans le second cas $\sum _{i=0}^{n+1} u_i =\frac{(m+1)(m+2)}{2} $, et dans le dernier cas $\sum _{i=0}^{n+1} u_i =\frac{m(m-1)}{2} $,
\end{solution}

\section{Egalité  \small[3 points] }
Soit A=$\{1,2,+\}$. Soit $Egal$ le sous ensemble de $A^+\times A^+$ composé de couple de mots représentant le même entier, par exemple les couples $(1,1)$, $(1+1,2)$ et $(1+1+2+1,2+2+1)$ appartiennent à $Egal$ alors que $(1,2)$ n'appartient pas à $Egal$. Donnez et prouvez une définition inductive de $Egal$.
\begin{copie}
\lignes{30}
\end{copie}
\begin{solution}
\begin{itemize}
\item Soit E l'ensemble défini par 
\item Base :  (1,1) , (1+1,2),  (2,2) appartiennent à E
\item Règles :


$(m,m')\in E \rightarrow (m',m) \in E$

$(m,m') \in E \rightarrow (m+1,m'+1) \in E$

$(m,m') \in E \rightarrow (1+m,1+m') \in E$

$(m,m') \in E \rightarrow (m+2,m'+2) \in E$

$(m,m') \in E \rightarrow (2+m,2+m') \in E$

$(m,m') \in E \rightarrow (1+m+1,m'+2) \in E$

$(m,m') \in E \rightarrow (1+m+1,2+m') \in E$

\item Clairement $E \subset Egal$.
\item Montrons $Egal \subset E$. 

Notons que si $(m,m')$ est dans Egal, les lettres de $m$ et $m'$ de rang impair sont égales soit à $1 $ soit à $2$ , tandis que les lettres de rang pair sont des +.

Montrons par récurrence sur $k$ que tout couple de mots $(m,m')$ de $Egal$  tel que le nombre total de $+$ dans m et m' est $ \leq k$  appartient à $E$.
Pour $k\leq 1$ le résultat est vrai, car (1,1) , (1,2) et (2,2) appartiennent à la base de $E$, et (2,1) appartient à E par la première règle.

Supposons le résultat vrai pour $k>=1$ et soit $(m,m')$ un couple de Egal  comportant $k+1$ $+$. Necessairement chacun des deux mots $m$ et $m'$ contient au moins un $+$.

Si $m$ et $m'$ commencent ou terminent tous les deux par $1$ ou tous les deux par $2$, alors par exemple $m=1+n$ et $m'=1+n'$ avec $(n,n')$ dans Egal et donc dans $E$ par réccurence. Il en résulte que $(m,m')$ est dans $E$.
On peut donc supposer $m=1+n$ et  $m'= 2+n'$. 
Si $n = p+1$, alors $m=1+p+1$, $m'=2+n'$ et $(p,n')$ appartient à $Egal$, donc $(p,n')$ appartient à $E$, donc $(m,m')$ appartient à $E$.
Sinon, $m=1+p+2$ et $m'=2+n'$ , et $(1+p,n')$ appartient à $Egal$, donc $(1+p,n')$ appartient à $E$, donc $(m,m')$ appartient à $E$.

\end{itemize}
\end{solution}
\end{document}
