Université de Nice-Sophia Antipolis École Supérieure en Sciences Informatiques

2004–2005

Controle de Mathématiques Discrètes du 4 Novembre 2004

Nom : Prénom : Groupe:

1

– 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

– La relation n’est pas symètrique. Par exemple si A = {1,3} et B = {5,7} on a ARB mais pas BRA

– La relation n’est pas antisymétrique.Par exemple si A = {1,3} et B = {1,7} on a ARB et BRA

– 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

– La relation R n’est pas une relation d’ordre

2

– La relation est reflexive : en effet (x,y)R(x,y), puisque x = x et y ≤ y

– La relation n’est pas symètrique. Par exemple on a (2,5)R(3,5) mais pas (3,4)R(2,5)

– 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 ≤ y′ et y′ ≤ y donc y = y′ et finalement (x,y) = (x′,y′)

– 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” ≤ y′ ≤ y et donc y” ≤ y et donc (x,y)R(x”,y”).

– 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 – x < x′ et alors (x,y)R(x′,y′)

– x′ < x et alors (x′,y′)R(x,y)

– x = x′. Comme y et y′ sont eux aussi comparables donc si y′ ≤ y on a (x,y)R(x′,y′), sinon on a (x′,y′)R(x,y)

3

– E ⊂ Egalab par induction structurelle toute simple

– Egalab ⊂ E par récurrence sur la longueur des mots de E – Le mot vide appartient bien à E

– Supposons que tout mot de Egalab de longueur inférieur à k soit dans E. Soit m un mot de Egalab de longueur k.

1. 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

2. 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.

– 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

4

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.

– C’est vrai pour un mot réduit à une lettre (la base de {0,1}^{+}).

– 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.

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

– C’est vrai pour la base, car f(f(m)) ne contient alors aucun facteur de longueur 5.

– 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

1. il comprend les 4 lettres de f(f(a)) et donc deux lettres identiques consécutives

2. il comprend les 3 premières lettres de f(f(a)) et donc deux lettres identiques consécutives

3. 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.

5

– toutDoubler(ϵ) = ϵ

– Pour toute lettre a et m dans A^{∗} : toutDoubler(am) = aatoutDoubler(m)

public mot toutDoubler(mot m){
if (m.vide()) {return m ;}
return m.pL().concat(m.pL()).concat(toutDoubler(m.fM()));
}

Soit E, l’ensemble définit inductivement par :

– Base : (0,0,0)

– Pour tout (n,0,0) dans E, (n + 1,0,0) est dans E

– Pour tout (n,m,0) dans E, (n,m + 1,0) est dans E

– Pour tout (n,m,p) dans E, (n,m,p + 1) est dans E 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 :

– application du troisième constructeur à (n,m,(p − 1)) si p > 0

– ou exclusif application du deuxième constructeur à (n,(m − 1),0) si p = 0 et m > 0

– ou exclusif application du premier constructeur à ((n − 1),0,0) si p = 0 et m = 0et n > 0 – ou exclusif est le triplet (0,0,0) 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.

7

Pour 3 pirates : 1/2, 1/3, 1/6 convient. Pour passer à 4 pirates, il y a plusieurs solutions :

– 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

– 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

– 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

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

1. 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.

2. 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)

3. 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))

Remarque : pour 2 pirates, ce n’est pas possible.