Université de Nice-Sophia Antipolis Polytech’ Nice Sophia

2005–2006

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

Nom : Prénom : Groupe:

Durée : 60 minutes

1 2 3 4 5 6

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.

Aucun document autorisé

1 Récurrence simple [2 points]

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

2 Des petits, des grands? [3 points]

On considère l’ensemble des parties de N ordonné par l’inclusion. Soit A = {{1,2},{1,5},{1,4}} et soit B = {{1,2},{1,2,3},{1},{1,4},{1,4,3}}

– A et B ont ils un ou des minorants ? 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 plus petits éléments ? 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 éléments maximaux ? si oui lesquels, si non pourquoi?

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

3 Ordre bien fondé [5 points]

Montrer que si un ensemble est ordonné par une relation d’ordre total bien fondé (c’est à dire un bon ordre), toute partie non vide admet un plus petit élément. Est-ce que la propriété est toujours vraie même si l’ordre n’est pas total (si oui prouver, si non donner un contre-exemple) ? Est-ce que la propriété est toujours vraie même si l’ordre n’est pas bien fondé (si oui prouver, si non donner un contre-exemple) ?

4 Définition inductive [3 points]

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

– Base : ϵ ∈ E

– Règles :

– Si m ∈ E alors 10m0 ∈ E – Si m ∈ E alors 01m0 ∈ E – Si m ∈ E alors 00m1 ∈ E

Soit M le sous-ensemble de {0,1}^{∗} formé des mots ayant deux fois plus de 0 que de 1. 1. A-t-on M inclus dans E?

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

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

5 Ordre inductif [4 points]

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

6 Maximal [3 points]

Montrer que pour un ordre quelconque (total ou partiel), toute partie finie non vide admet au moins un élément maximal.