Université de Nice-Sophia Antipolis Polytech’ Nice Sophia

2005–2006

Contrôle de Mathématiques Discrètes du 12 Octobre 2005

Nom : Prénom : Groupe:

Durée : 1 heure

1 2 3 4 5 6

Toutes vos réponses doivent être justifiées par une démonstration ou un contre-exemple. Aucun document autorisé

1 Récurrence simple

Montrer par récurrence que pour tout n entier strictement positif la somme des n premiers entiers multiples de trois et impairs est egal à 3n^{2}

– Base n=1 , le premier entier impair multiple de 3 est 3, et on a bien 3 = 3.1^{2}

– On suppose que ∑_{0}^{n−1} 6k + 3 = 3n^{2}.

– On a alors ∑_{0}^{n} 6k + 3 = 3n^{2} + 6n + 3 = 3(n + 1)^{2}.

2 Des petits , des grands?

On considère l’ensemble des parties de N ordonné par l’inclusion. Soit A = {{a,b},{a,b,d},{a,d}} et soit B = {{a,b},{a,b,c},{a}}

– 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 plus é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 plus éléments maximaux ? si oui lesquels, si non pourquoi?

– L’ensemble des minorants de A ={∅,{a}}

– L’ensemble des minorants de B ={∅,{a}}

– A n’ a pas de plus petit élément puisqu’aucun de ses minorants ne lui appartient, tandis que B a {a} comme plus petit élément.

– L’ensemble des éléments minimaux de A ={{a,b},{a,d}}

– L’ensemble des éléments minimaux de B ={{a}}

– L’ensemble des majorants de A ={E ⊂ N/{a,b,d} ⊂ E}

– L’ensemble des majorants de B ={E ⊂ N/{a,b,c} ⊂ E}

– Le plus grand élément de A est {a,b,d}, tandis que le plus grand élément de B est {a,b,c} – {a,b,d} est l’unique élément maximal de A et {a,b,c} est l’unique élément maximal de B.

3 Ordre bien fondé

Une relation d’ordre est telle que pour tout élément x, il existe un nombre fini d’éléments inférieurs à x, cette relation est elle bien fondée ? La réciproque est elle vraie?

Oui si l’on considére une suite strictement décroissante, son nombre de termes est borné par le nombre d’éléments (fini) qui sont inférieurs à son premier terme La réciproque est fausse, on en a vu des exemples en cours , par exemple l’ordre lexicographique sur NxN est bien fondé, mais tous les couples de la forme (1,n) sont plus petits que 2,1).

4 Définition inductive

On considère l’ensemble E défini de manière inductive par

– Base : ϵ ∈ E

– Règles :

– Si m ∈ E alors 10m ∈ E

– Si m ∈ E alors 01m ∈ E

– Si m ∈ E alors m10 ∈ E

– Si m ∈ E alors m01 ∈ E Soit M le sous-ensemble de {0,1}^{∗} formé des mots ayant autant de 0 que de 1.

1. A-t-on M inclus dans E?

2. A-t-on E inclus dans M?

3. Montrer que le schéma définissant E n’est pas libre

4. Modifier le schéma pour le rendre libre (sans modifier l’ensemble E obtenu, bien sûr)

5. Donner (sans preuve ) un schéma inductif pour M

1. M n’est pas inclus dans E, car 1100 est dans M mais pas dans E

2. E est inclus dans M. Il suffit d’utiliser l’induction structurelle et de montrer – ϵ ∈ M

– Si m ∈ M alors 10m ∈ M

– Si m ∈ M alors 01m ∈ M

– Si m ∈ M alors m10 ∈ M

– Si m ∈ M alors m01 ∈ M

3. Le schéma définissant E n’est pas libre, car le mot 1010 peut être construit par la règle 1 ou la règle 3.

4. Si l’on conserve uniquement les deux premieres règles on obtient un schéma libre pour le même ensemble: Soit F défini par

– ϵ ∈ F

– Si m ∈ F alors 10m ∈ F

– Si m ∈ F alors 01m ∈ F Le schéma définissant F est libre car

– ϵ ne peut être produit par aucune des deux règles – ∀m,m′ ∈ F, 10m ≠ 01m′

– ∀m,m′ ∈ F, 10m = 10m′ ⇒ m = m′

– ∀m,m′ ∈ F, 01m = 01m′ ⇒ m = m′ Clairement F ⊂ E. Montrons E ⊂ F par induction structurelle sur E

– ϵ appartient à F

– Si m ∈ F, alors 10m ∈ F : évident – Si m ∈ F, alors 01m ∈ F : évident

– P(m) : Si m ∈ F, alors m10 ∈ F : pas évident !

mais on va le montrer par induction structurelle sur F – Pour m = ϵ on a bien 10 ∈ F, donc P (ϵ) est vraie

– Supposons P (m) et montrons P (10m). Soit 10m dans F. Puisque le schéma définissant F est libre, 10m a été construit à partir de m et de la règle 1 et donc m est dans F. Mais alors puisque P(m) est vrai, m10 ∈ F. Par définition de F, on sait que 10m10 est alors dans F. On a donc bien P (10m) vrai

– Supposons P (m) et montrons P (01m).

Soit 01m dans F. Puisque le schéma définissant F est libre, 01m a été construit à partir de m et de la règle 2 et donc m est dans F. Mais alors puisque P(m) est vrai, m10 ∈ F. Par définition de F, on sait que 01m10 est alors dans F. On a donc bien P (01m) vrai

– Si m ∈ F, alors 01m ∈ F : se montre exactement comme l’implication précédente On a donc bien E = F, et l’on a donc trouvé un schéma libre définissant E

5. Un schéma possible pour M – ϵ appartient à M

– m,m′ ∈ M → Om1m′ ∈ M

– m,m′ ∈ M → 1m0m′ ∈ M

5 Plus petit que

Donner et prouvez un schéma inductif pour P = {(m,n) ∈ N^{2},m ≤ n}

– Base {0,0} ∈ S

– {(p,q) ∈ S ⇒ (p + 1,q + 1) ∈ S

– {(p,q) ∈ S ⇒ (p,q + 1) ∈ S Montrons P = S

– S ⊂ P se montre facilement par induction structurelle sur S, il suffit de vérifier que – Base 0 ≤ 0

– p ≤ q ⇒ p + 1 ≤ q + 1

– p ≤ q ⇒ p ≤ q + 1

– P ⊂ S On va montrer par récurrence sur k, la propriété

P (k) = ∀(m,n) ∈ N,m + n ≠ k,m ≤ n, on a (m,n) ∈ S – Base k=0, P(0) est vraie car (0,0) ∈ S

– On suppose P(k) vraie.

Soit un couple (m,n) ∈ N,m + n ≠ k + 1,m ≤ n. Le seul cas à considérer est le cas où m + n = k + 1.

– Si n=m , alors le couple (m − 1,n − 1) est un couple d’entiers (on ne peut pas avoir m = n = 0 et m + n = k + 1 ) qui vérifie m + n − 2 < k et donc par hypothèse de récurrence c’est un couple de S, par définition de S, le couple (m,n) est lui aussi dans S .

– Si m < n, alors m ≤ n − 1, (m,n − 1) est un couple d’entiers (n ne peut pas etre nul puisque m < n) et m + n − 1 ≤ k. Donc par hypothèse de récurrence c’est un couple de S, par définition de S, le couple (m,n) est lui aussi dans S .

Bien sur d’autres schémas sont possibles.

6 Maximal unique

Montrer que pour un ordre quelconque (total ou partiel), toute partie finie admettant un unique élément maximal, admet un plus grand élément.

Démontrons par récurrence sur k la propriété P (k) :toute partie finie de cardinal k admettant un unique élément maximal, admet un plus grand élément

– n = 1, l’unique élément est à la fois maximal et plus grand élément de l’ensemble

– Supposons P (n) vrai, pour n ≥ 1. Soit A une partie de cardinal n+1 admettant uniqmaximalA comme unique élément maximal. Soit x_{0} un élément de A, différent de uniqmaximalA. Considerons A′ = A − {x_{0}}. uniqmaximalA est maximal dans A′. Supposons que A′ admette un autre élément maximal, autremaxA′. Puisque autremaxA′ n’est pas maximal dans A, c’est que autremaxA′ < x_{0}. D’autre part, aucun élément de A′ n’est plus grand que autremaxA′, donc aucun élément de A n’est plus grand que x_{0}, et donc x_{0} est aussi maximal dans A, contradiction. A′ a donc un unique élément maximal, et par hypothèse de récurrence, A′ admet uniqmaxA comme plus grand élément. Comme x_{0} n’est pas maximal dans A, il existe M′ dans A et donc dans A′, tel que x_{0} < M′, comme uniqumaxA est le plus grand élément de A′, on a M′ < uniqmaxA, et donc x_{0} < uniqmaxA, et donc uniqmaxA est le plus grand élément de A.

Remarque : la démonstration devient triviale, si l’on suppose que l’ordre est total.