Université de Nice-Sophia Antipolis Polytech’ Nice Sophia

2005–2006

Contrôle de Mathématiques Discrètes du 28 Septembre 2005

Nom : Prénom : Groupe:

Durée : 60 minutes

1 2 3 4 5 6 7

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

1 Récurrence simple

Montrez par récurrence, que quelque soit un entier naturel n, la somme des n premiers nombres impairs est égal à n^{2}.

La somme des n premiers nombres impairs peut s’écrire au choix ∑_{i=1}^{n}(2i−1) ou ∑_{i=0}^{n−1}(2i+1).

– Base n=0 , la somme de 0 entiers est bien nulle.

– Supposons que l’on ait ∑_{i=0}^{n−1}(2i + 1) = n^{2}, alors ∑_{i=0}^{n}(2i + 1) = ∑_{i=0}^{n−1}(2i + 1) + 2n + 1 = n^{2} + 2n + 1 = (n + 1)^{2}

2 Plus grand élément

Démontrer que toute partie finie non vide d’un ensemble totalement ordonné contient un plus grand élément.

Preuve par l’absurde : Supposons qu’il existe une partie finie E′ d’un ensemble totalement ordonné (E,≤) qui ne contienne aucun plus grand élément. Nous allons construire une suite infinie u_{n} strictement croissante d’éléments de E′, ce qui contredit E′ fini.

Soit u un élément de E′ , on pose u = u_{1}. Supposons que la suite (strictement croissante) soit construite jusqu’au rang n. Puisque E’ n’admet pas d’élément maximum, c’est qu’il existe un élément v dans E′ tel que v ≤ u_{n} soit faux. Puisque l’ordre est total cela signifie que l’on a u_{n} < v, on peut donc choisir u_{n+1} = v pour construire la suite au rang n + 1. La suite est donc infinie.

3 Plus grand élément

On considère sur IN, la relation est multiple de notée emd définie par a emd b si il existe un entier k tel que a = kb . Montrer que emd est une relation d’ordre.

Est-ce un ordre total ? Donner s’ils existent le plus petit et le plus grand élément de IN pour emd.

C’est une relation d’ordre partiel .

En effet la relation est :

– reflexive puisque pour tout entier n, on a n emd n

– transitive: si n emd m et m emd q, alors n emd q

– antisymétrique : si n emd m et m emdn, alors si n ou m est nul, l’autre l’est aussi, sinon

n ≤ m et m ≤ n (pour la relation d’ordre usuelle) et donc n = m L’ordre est partiel puisque l’on n’a ni 2 emd 5, ni 5 emd 2.

Quelque soit k entier, on a k emd 1 et 0 emd k, donc 0 est le minimum de IN pour la relation emd tandis que 1 est le maximum.

4 Ordre ?

Donner la définition d’une relation d’ordre et donner un exemple de relation d’ordre (différent de ceux vus en cours/TD).

Un ordre est une relation binaire, reflexive, antisymmétrique et transitive. Comme exemple de relation d’ordre non vue en cours , on peut par exemple choisir sur l’ensemble des mots sur un alphabet A, la relation mRm’ si et seulement si m est un sous mot de m’ (par exemple bra R abracadabra)

5 Ordre strict?

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 à toutes les courses de l’UCI pro-tour où l’un et l’autre ont couru, autrement dit dès que x et y courent ensemble x arrive devant y. Il n’y a aucun ex eaquo dans le système de classement UCI. Est-ce une relation d’ordre strict ? Même question si l’on suppose en outre que tous les coureurs participent à toutes les courses.

Si l’on ne suppose pas que tous les coureurs participent à toutes les courses, on peut etre dans le cas ou x est arrivé avant y dans la seule course qu’ils ont tous les deux couru, tandis que y et z n’ont couru ensemble que sur une autre course lors de la quelle y est arrivé avant z . Il est alors tout a fait possible que x et z n’aient jamais couru ensemble, ou bien qu’ils aient couru ensemble lors d’une troisième course où z est arrivé avant x.

La relation n’est donc pas transitive. En revanche elle est antisymétrique (puisqu’il n’y a jamais d’ex aequo) et antireflexive (nul n’arrive avant lui même)

En revanche si tous les coureurs ont participé à toutes les courses, la relation devient transitive, et il s’agit donc d’un ordre strict. Cet ordre strict est aussi partiel, puisque sauf s’il n’y a qu’une course, il est possible que x et y ne soient pas toujours classés dans le même ordre.

6 Bavardage

On considère E l’ensemble des SI1 et des MAM1. Soient a et b deux éléments de E, on dit que aRb si et seulement si a a déjà eu une conversation avec b. La relation R est elle un ordre ? Pour chacune des propriétés d’une relation d’ordre dire si R vérifie la propriété. Si R est une relation d’ordre est ce un ordre total ou partiel ?

La relation n’est pas reflexive ( sauf si tout le monde parle tout seul), elle n’est pas transitive, et elle est symétrique mais pas antisymétrique. Ce n’est donc pas une relation d’ordre.

7 Calculateur prodige (d’après un problème du journal Le Monde

Un magicien demande à un spectateur de choisir 2 nombres, et de les écrire sur une feuille l’un en dessous de l’autre, puis d’en faire la somme et de l’écrire en dessous du dernier nombre écrit, puis de faire la somme du nombre obtenu et du nombre précédent et de l’écrire en dessous du dernier nombre écrit, puis de recommencer autant de fois qu’il veut. Le magicien lui demande ensuite le deuxième nombre choisi ainsi que les 2 derniers nombres qu’il a écrit, et après invocation d’une formule magique (!), lui donne la somme de tous les nombres que le spectateur a écrit. Quelle est la formule magique du magicien ?

En notant f_{n} le n^{ieme} nombre écrit par le spectateur, on a pour entier n, la relation f_{n+2} = f_{n+1} + f_{n} (suites dites de Fibonacci). Il s’agit donc de trouver un formule pour calculer la somme des termes d’une suite de Fibonacci, S_{n} = ∑_{i=1}^{n} f_{i}. En sommant les égalités f_{i+2} = f_{i+1} +f_{i}, pour tous les i variant de 1 à n, on trouve après simplications que f_{n+2} = f_{1} + S_{n}, soit S_{n} = f_{n+2} − f_{1}. Cette égalité peut être trouvée ou devinée par tout autre moyen (par exemple, en regardant ce qui se passe pour quelques termes), puis démontrée facilement par récurrence.

Si on revient au magicien, il cherche à calculer S_{n}, pour cela il demande f_{n} et f_{n−1} qui lui permettent de calculer f_{n+2} = f_{n+1} + f_{n} = 2f_{n} + f_{n−1}, auquel il soustrait le deuxième nombre écrit f_{2} (et non le premier comme indiqué par erreur dans l’énoncé original).