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

2004–2005

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

Aucun document autorisé

Note :

Nom : Prénom : Groupe:

Durée : 2 heures

1 2 3 4 5 6 7

Toutes vos réponses doivent être justifiées. Le barême est donné à titre indicatif

1 2 points

Soit (E,≤) un ensemble ordonné. Soit R la relation sur P(E) \ {∅} définie par : ARB ⇔ ∃a ∈ A,∃b ∈ B,a ≤ 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 ?

2 2 points

Soit (E,≤) un ensemble muni d’une relation d’ordre total. Soit R la relation sur E × 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} ≤ 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 ?

3 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

– Base : ϵ appartient à E

– Règles :

– si m appartient à E alors amb appartient à E

– si m appartient à E alors bma appartient à E

– si m et m′ appartienent à E alors mm′ appartient à E

1. Montrez que E égal Egalab

2. Le schéma définissant E est-il libre?

4 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 ∈ {0,1}^{+} et toute lettre l ∈ {0,1}, f(ml) = f(m)f(l)

1. Montrer par induction structurelle que pour tout mot m de {0,1}^{+}, f(m) ne contient pas trois lettres consécutives identiques.

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

5 4 points

Soit A un alphabet, définir inductivement la fonction toutDoubler : A^{∗} → 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.

6 2 points

Donner (et prouver) une définition inductive libre de N × N × N

7 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 ?