\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 4 Novembre 2004}%{Dur\'{e}e : 55  minutes}% \
%{Probabilit\'{e}s}{02}{03}{du 1er Avril  2003 }¨%\\
%\addtolength{\evensidemargin}{-1cm}
%\addtolength{\oddsidemargin}{-1cm}
%\\
\section{}
\begin{itemize}
\item La relation est reflexive : en effet puisqu'on ne considère pas d'ensemble vide, il suffit de choisir $a=b$ égal à n'importe quel élément de l'ensemble
\item La relation n'est pas symètrique. Par exemple si $A=\{1,3\}$ et $B=\{5,7\}$ on a $ARB$ mais pas $BRA$
\item La relation n'est pas antisymétrique.Par exemple si $A=\{1,3\}$ et $B=\{1,7\}$ on a $ARB$ et $BRA$
\item La relation n'est pas transitive. Par exemple si $A=\{4,5\}$ , $B=\{1,7\}$  et $C=\{2,3\}$, on a $ARB$, $BRC$, mais pas $ARC$
\item La relation $R$ n'est pas une relation d'ordre 
\end{itemize}
\section{ }
\begin{itemize}
\item La relation est reflexive : en effet $(x,y)R(x,y)$, puisque $x=x$ et $y \leq y$
\item La relation n'est pas symètrique. Par exemple on a  $(2,5)R(3,5)$ mais pas $(3,4)R(2,5)$
\item La relation est antisymétrique. Si l'on a $(x,y)R(x',y')$ et $(x',y')R(x,y)$, alors c'est que forcement $x=x'$ (puisque l'on ne peut pas avoir simultanément $x<x'$ et $x'<x$). On a donc $y \leq y'$ et $y'\leq y$ donc $y=y'$ et finalement $(x,y)=(x',y')$
\item La relation est  transitive. Supposons que l'on ait $(x,y)R(x',y')$ et $(x',y')R(x",y")$ . Si $x<x'$ alors dans tous les cas, on aura $x<x"$, et donc $(x,y)R(x",y")$. Sinon c'est que $x=x'$. Si $x'<x"$, alors on a aussi $x<x"$ et donc $(x,y)R(x",y")$. Sinon $x=x'=x"$, et on a alors $y" \leq y' \leq y$ et donc $y"\leq y$ et donc $(x,y)R(x",y")$.
\item La relation $R$ est donc bien une relation d'ordre. C'est une relation d'ordre totale, en effet considérons $(x,y)$ et $(x',y')$. x et x' sont comparables donc on a l'un des trois cas suivants
\begin{itemize}
\item  $x<x'$ et alors $(x,y)R(x',y')$
\item  $x'<x$ et alors $(x',y')R(x,y)$
\item $x=x'$. Comme $y$ et $y'$ sont eux aussi comparables donc si $y' \leq y$ on a $(x,y)R(x',y')$, sinon on a $(x',y')R(x,y)$
\end{itemize}
\end{itemize}
\section { }
\begin{itemize}
\item  $E \subset Egalab$ par induction structurelle toute simple
\item  $Egalab \subset E$ par récurrence sur la longueur des mots de $E$
\begin{itemize}
\item Le mot vide appartient bien à $E$
\item Supposons que tout mot de $Egalab$ de longueur  inférieur à $k$ soit dans $E$. Soit $m$ un mot de $Egalab$ de longueur $k$.
\begin{enumerate}
\item Si $m=am'b$ ou $bm'a$, alors $m'$ est aussi un mot de $Egalab$, comme la longueur de $m'$ est strictement inférieur à $k$, $m'$ est par hypothèse dans $E$. Par définition de $E$, $m$ est donc aussi dans $E$
\item Si $m'=ama$ ou $bmb$, on utilise un compteur qui sur tous les prefixes de m détermine le nombre de a moins le nombre de b. Ce compteur vaut 0 à la fin du mot. D'après la forme de $m'$ le compteur vaut 1 sous la premiere lettre et -1 sous l'avant dernière ou le contraire. En tous les cas, il existe un prefixe $p$ de $m'$ sous lequel le compteur vaut 0. SOit $s$ tel que $m=ps$.$p$ et $s$ sont deux mots de $Egalab$ de longueur inférieur à $k$, ce sont donc deux mots de $E$ et donc par définition de $E$, $m' $ appartient à $E$.
\end{enumerate}
\end{itemize}
\item Le schéma définissant $E$ n'est pas libre. Par exemple $abab$ peut etre obtenu à partir de $ba$ en ajoutant un $a$ devant et un $b$ derrière ou bien à partir des deux mots $ab$ et $ab$
\end{itemize}

\section {}
Montrons par induction structurelle que pour tout mot $m$ de $\{0,1\}^+$, f(m) ne contient pas trois lettres consécutives identiques, et que ses deux dernieres lettres sont soit $01$ soit $10$.
\begin{itemize}
\item C'est vrai pour un mot réduit à une lettre (la base de $\{0,1\}^+$).
\item On suppose que c'est vrai pour $m$, alors verifions le pour $ma$ où $a$ est une lettre. Clairement $f(ma)$ termine par $01$ ou $10$. D'autre part, $f(m)$ ne contient pas trois lettres identiques consécutives. Donc il suffit de regarder ce qui se passe quant on prend trois lettres qui ne sont pas toutes dans $f(m)$. Si on prend seulement les deux dernières lettres de $f(m)$ (plus la premiere lettre de $(a)$), alors celles-ci ne sont pas identiques, donc tout va bien. Si on prend seulement la dernière lettre de $f(m)$, comme $f(a) $ est composé de deux lettres différentes, tout va bien aussi. Donc $f(ma)$ ne comporte pas trois lettres consécutives identiques.
\end{itemize}

Montrons par induction structurelle que pour tout mot $m$ de $\{0,1\}^+$, tout facteur (c'est à dire tout sous mot) de longueur au moins $5 $ de $(f(m))$ contient deux '0' ou deux '1' consécutifs, et de plus que ses $4$ dernières lettres sont 0110 ou 1001

\begin{itemize}
\item C'est vrai pour la base, car $f(f(m))$ ne contient alors aucun facteur de longueur $5$.
\item Supposons que ce soit vrai pour $m$ et montrons que c'est vrai pour $f(f(ma)$, c'est à dire pour $f(f(m))f(f(a))$. Tout d'abord $f(f(a))$ est bien $0110$ ou $1001$ . Considèrons un facteur de longueur $5$ de $f(f(ma))$. Si c'est aussi un facteur de $f(f(m))$, alors il contient deux lettres identiques consécutifs. Sinon on est dans un des 3 cas suivants
\begin{enumerate}
\item il comprend les 4 lettres de $f(f(a))$ et donc deux lettres identiques consécutives
\item il comprend les 3 premières lettres de $f(f(a))$ et donc deux lettres identiques consécutives
\item il comprend  seulement une ou deux  des premières lettres de $f(f(a))$, et donc les trois dernières lettres de $f(f(m))$, et donc deux letters identiques consécutives.
\end{enumerate}
\end{itemize}

\section {}




 
{\it
 \begin{itemize}
 \item $toutDoubler(\epsilon) = \epsilon $
 \item Pour toute lettre $a$ et $m$ dans $A^*$ : $toutDoubler(am) =aa toutDoubler(m)$
 \end{itemize}
 }
 \begin{verbatim}
 
 public mot toutDoubler(mot m){
 	if (m.vide()) {return m ;}
 	return m.pL().concat(m.pL()).concat(toutDoubler(m.fM()));
 }
 \end{verbatim}							   



\section {}

Soit $E$, l'ensemble définit inductivement par :
{\it
 \begin{itemize}
 \item Base : $(0,0,0)$
 \item Pour tout $(n,0,0)$ dans $E$, $(n+1,0,0)$ est dans $E$
 \item Pour tout $(n,m,0)$ dans $E$, $(n,m+1,0)$ est dans $E$
 \item Pour tout $(n,m,p)$ dans $E$, $(n,m,p+1)$ est dans $E$
 \end{itemize}
 }

Il est évident que $E$ est inclus dans N x N x N.
Il est aussi évident que tout triplet $(n,m,p)$ de N x N x N est obtenu à partir de $(0,0,0)$ 
par application de $n$ fois le premier constructeur, puis $m$ fois le deuxième, 
puis $p$ fois le troisième.

Par ailleurs, le schéma est libre, car $(n,m,p)$ ne peut être obtenu que par :
\begin{itemize}
\item application du troisième constructeur à $(n,m,(p-1))$ si $p > 0$
\item ou exclusif application du deuxième constructeur à $(n,(m-1),0)$ si $p = 0$ et $m > 0$
\item ou exclusif application du premier constructeur à $((n-1),0,0)$ si $p = 0$ et $m = 0$et $n > 0$
\item ou exclusif est le triplet $(0,0,0)$
\end{itemize}


Attention : grâce aux coordonnées nulles, 
les constructeurs donnés imposent l'ordre dans lequel ils doivent être appliqués.
Sans ces coordonnées nulles, on obtient un schéma correct mais qui n'est pas libre.
Un tel schéma a été donné par beaucoup d'entre vous.





\section{}


Pour 3 pirates : 1/2, 1/3, 1/6 convient.

Pour passer à 4 pirates, il y a plusieurs solutions :
\begin{itemize}
\item donner la moitié au capitaine, et rediviser la moitié restante selon le partage précédant,
ce qui donne 1/4, 1/6, 1/12
\item ne pas toucher aux deux premières parts, et partager la dernière part (1/6) en 2/3, 1/3,
ce qui donne 1/9, 1/18
\item ne pas toucher aux deux premières parts, et partager la dernière part (1/6) en 1/7, et 1/6 - 1/7
ce qui donne 1/7, 1/42
\end{itemize}

De manière générale, si l'on a une solution pour N pirates, on a aussi une solution pour N+1 pirates, soit 
\begin{enumerate}
\item En donnant la moitié du butin au capitaine, puis en redistribuant le reste R du butin aux N pirates restant, comme si l'on avait du repartir R entre N pirates.
\item Ne pas toucher à la répartition pour les N-1 premiers pirates et diviser la derniere part 1/2k en 1/3k et 1/6k (notez que 6k est aussi un nombre pair)
\item soit ne pas toucher à la repartition pour les N-1 premiers pirates, et partager la dernière part 1/k en deux parts, 1/k+1 et 1/(k(k+1))
\end{enumerate}


Remarque : pour 2 pirates, ce n'est pas possible.
\end{document}