\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{\'{E}cole Sup\'{e}rieure en Sciences
Informatiques}
{ }{04}{05}{Math\'{e}matiques  Discr\`{e}tes\\ du 15 Novembre 2004}{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}
}
\\

Toutes vos réponses doivent être justifiées.

Le barême est donné à titre indicatif




\section {2 points}
Soit (E,$ \leq $) un ensemble ordonn\'{e}. Soit $R$ la relation sur $\mathcal{P}(E)\setminus \{\varnothing \}$ d\'{e}finie par :


\mbox{
$A R B \Leftrightarrow \exists a \in A, \exists b \in B, a\leq b$
}.
La relation $R$ est-elle reflexive, symétrique, antisymétrique, transitive ? 
Est-une relation d'ordre ?  Si oui, est ce un ordre total ou partiel ? 
\begin{copie}
\lignes{12}
\end{copie}
\section{ 2 points}
Soit (E,$ \leq $) un ensemble muni d'une relation d'ordre total. Soit $R$ la relation sur $E \times E$ définie par
$(x_1,y_1)R(x_2,y_2) $ si et seulement si $x_1 <x_2$ ou $x_1=x_2 $ et $ y_2 \leq y_1$. La relation $R$ est-elle reflexive, symétrique, antisymétrique, transitive? 
Est-une relation d'ordre ?  Si oui, est ce un ordre total ou partiel ? 

\begin{copie}
\lignes{12}
\end{copie}

\section {4 points }
Soit $A=\{a,b\}$. Soit $Egalab$, le sous ensemble de $A^*$ formé des mots ayant autant de a que de b. 

On considère l'ensemble E défini de manière inductive par
\begin{itemize}
\item Base : $\epsilon$ appartient à $E$
\item Règles :
\begin{itemize}
\item si $m$ appartient à $E$ alors $amb$ appartient à $E$
\item si $m$ appartient à $E$ alors $bma$ appartient à $E$
\item si $m$ et $m'$ appartienent à $E$ alors $mm'$ appartient à $E$
\end{itemize}
\end{itemize}
\begin{enumerate}
\item Montrez que $E$ égal $Egalab$
\item Le schéma définissant $E$ est-il libre?
\end{enumerate}
\begin{copie}
\lignes{16}
\end{copie}

\section {4 points}
On défini inductivement la fonction $f$ de $\{0,1\}^+$ dans $\{0,1\}^+$
par $f(0)=01$ et $f(1)=10$ et pour tout mot $m \in \{0,1\}^+$ 
et toute lettre $l \in \{0,1\}$, \mbox{$f(ml) = f(m)f(l)$}
\begin{enumerate}
\item
Montrer par induction structurelle que pour tout mot m de $\{0,1\}^+$, f(m) ne contient pas trois lettres consécutives identiques.
\item
Montrer que pour tout mot m de $\{0,1\}^+$, tout facteur de longueur au moins 5 de f(f(m))  contient deux '0' ou deux '1' consécutifs.
\end{enumerate}
\begin{copie}
\lignes{16}
\end{copie}

\section {4 points}



Soit $A$ un alphabet, définir inductivement la fonction

$toutDoubler : A^* \rightarrow A^*$

telle que $toutDoubler(m)$ est le mot obtenu à partir de $m$ en remplaçant chaque lettre, par la lettre répétée deux fois. Par exemple, $toutDoubler(abc)=aabbcc$


Donner aussi un code récursif.


 
\begin{copie}
\lignes{16}
\end{copie}



\section {2 points}
Donner (et prouver) une définition inductive libre de $N \times N \times N$

\begin{copie}
\lignes{16}
\end{copie}

\section {3 points : Le pirate égyptologue (Source Le Monde, 28/9/1999)}

Le capitaine d'un vaisseau pirate, qui s'est entiché de la civilisation égyptienne, a découvert que chez les anciens Egyptiens, on n'utilisait que des fractions dont le numérateur valait 1.
Depuis, il exige que le partage du butin après un pillage attribue toujours aux membres de l'équipage une fraction de butin différente et de numérateur 1. Ainsi, lui-même s'attribue la part la plus importante, son second une part inférieure, et ainsi de suite... Si la répartition s'avère impossible selon ce principe, le butin est restitué aux malheureuses victimes.
Comment s'opère le partage si les pirates sont trois ?
S'ils sont quatre ? S'ils sont cinq ?

Le partage du butin selon cette règle est-il possible quel que soit le nombre de pirates, si oui comment ? 
\begin{copie}
\lignes{16}
\end{copie}

\end{document}