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

2 Plus grand élément

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

3 Plus grand élément

On considère sur IN, la relation est multiple de notée emd définie par aemdb 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.

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

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.

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 ?

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