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

2005–2006

Examen Mathématiques Discrètes du 16 Novembre 2005

Tous documents autorisés

Durée : 2 heures

1 2 3 4 5 6 7

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.

1 Encadrement [2 points]

Soit (E, ≤) 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 ≤ x ≤ M

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 ≤ x ≤ 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 ≤ 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 ≤ 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.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Cyclistes [2 points]

1. Sur l’ensemble des cyclistes professionnels, on considère la relation 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?

2. On considère maintenant la relation 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?

1. 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 ⇒ b est vrai dès que a est faux)

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Des petits, des grands? [3 points]

On considère l’ensemble N ordonné par la divisibilité, c’est à dire x ≤ 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.

– A et B ont ils un ou des minorants? si oui lesquels, si non pourquoi?

– A et B ont ils un ou des plus petits éléments? si oui lesquels, si non pourquoi?

– A et B ont ils un ou des éléments minimaux? si oui lesquels, si non pourquoi?

– A et B ont ils un ou des majorants? si oui lesquels, si non pourquoi?

– A et B ont ils un ou des plus grands éléments? si oui lesquels, si non pourquoi?

– A et B ont ils un ou des éléments maximaux? si oui lesquels, si non pourquoi?

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.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Fibonnacci [4 points]

1. 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 ≥ 2. Montrez que f_{k} est pair si et seulement si k est un multliple de trois.

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

3. Montrer que pour tout n, n ≥ 1, u_{n} = bf_{n} + af_{n−1}

1. On montre par récurrence sur k que pour tout i ≤ 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 ≥ 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.

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

3. Pour n = 1 on a bien u_{1} = bf_{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.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Définitions inductives [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.

1. Soit E l’ensemble défini inductivement par

Base : ϵ ∈ E Règles :

–– m ∈ E → 0m ∈ E

– m ∈ E et m ≠ 0m′, → m0 ∈ E

– m ∈ E → 1m1 ∈ E

– E ⊂ UP Se montre facilement par induction structurelle :

ϵ ∈ 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

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

– Ce schéma est libre, en effet, ϵ 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.

2. – Soit E l’ensemble défini inductivement par Base : ϵ ∈ E Règles : m ∈ E → 00m ∈ E m ∈ E → m00 ∈ E m ∈ E → m11 ∈ E m ∈ E → 11m ∈ E m ∈ E → 1m1 ∈ E m ∈ E → 0m0 ∈ E m ∈ E → 01m01 ∈ E m ∈ E → 10m10 ∈ E

– E ⊂ P Se montre facilement par induction structurelle :

– P ⊂ E ϵ ∈ 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

– 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

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

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

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

– sinon m = 01m”1, m" ne peut pas être vide, sa dernière lettre est soit 0 soit 1. – 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.

– sinon m = 01p11, et 01pappartient à P. Par hypothèse de récurrence p est donc dans E et donc par définition de E on a m dans E.

Le cas où m commence par 1 se traite de manière analogue

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 Récurrence [3 points]

Soit u_{n} une suite d’entiers relatifs, telle que pour tout n, ∑_{i=0}^{n} u_{i}^{3} = (∑_{i=0}^{n} u_{i})^{2}. Montrez que pour tout entier n , il existe m dans N, tel que ∑_{i=0}^{n} u_{i} = \frac{m(m+1)}{2}. 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 ∑_{i=0}^{n+1} u_{i}^{3} = ∑_{i=0}^{n} u_{i}^{3} + u_{n+1}^{3} =

(\frac{m(m+1)}{2})^{2} + u_{n+1}^{3} = (∑_{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, ∑_{i=0}^{n+1} u_{i} = \frac{m(m+1)}{2}, dans le second cas ∑_{i=0}^{n+1} u_{i} = \frac{(m+1)(m+2)}{2}, et dans le dernier cas ∑_{i=0}^{n+1} u_{i} = \frac{m(m−1)}{2},

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 Egalité [3 points]

Soit A={1,2,+}. Soit Egal le sous ensemble de A^{+}×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.

– Soit E l’ensemble défini par

– Base : (1,1) , (1+1,2), (2,2) appartiennent à E

– Règles :

(m,m′) ∈ E → (m′,m) ∈ E (m,m′) ∈ E → (m + 1,m′ + 1) ∈ E (m,m′) ∈ E → (1 + m,1 + m′) ∈ E (m,m′) ∈ E → (m + 2,m′ + 2) ∈ E (m,m′) ∈ E → (2 + m,2 + m′) ∈ E (m,m′) ∈ E → (1 + m + 1,m′ + 2) ∈ E (m,m′) ∈ E → (1 + m + 1,2 + m′) ∈ E

– Clairement E ⊂ Egal.

– Montrons Egal ⊂ 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 ≤ k appartient à E. Pour k ≤ 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.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .