Précédent / Suivant / Table des matières

 

Exercice I : (Principe des cages à pigeons)

1) Soit nN*. On considère la proposition p(n) : « En distribuant n+1 lettres dans n boîtes à lettres l’une de ces boîtes au moins contiendra au moins 2 lettres ».
     a) Démontrer  p(n) par l’absurde.

     b) Démontrer  p(n) par récurrence.
2) Un enfant doit colorier 7 jetons. Il ne dispose que de deux couleurs (rouge et bleu). Expliquer pourquoi il obtient une partition de l’ensemble des 7 jetons en deux sous-ensembles de jetons de même couleur dont l’un contient au moins 4 jetons.
3) Que peut-on dire de la partition obtenue par l’enfant s’il dispose de 3 couleurs ?
Notation : Soit xR⁺ On note  [[x]]  le plus petit entier naturel supérieur ou égal à x. Exemple : [[2,73]]=3 ; [[7/2]]=4 ; [[5]]=5.
4) Soit E un ensemble fini contenant n éléments (nN*) et soit {S₁, S₂, …, S_k} une partition de E en k parties. On considère la proposition p : « au moins une partie contient au moins [[n/k]] éléments »
     a) Ecrire formellement p.

     b)             Démontrer  p par l’absurde.
5) Application : Une soirée mondaine réunit n personnes. Chaque personne présente peut connaître ou ne pas connaître chacune des n-1 autres personnes. On suppose que cette relation est symétrique (si A connaît B alors B connaît A).
Montrer que dans cette soirée il y a au moins deux personnes qui connaissent exactement le même nombre de personnes présentes.

 

Exercice II :

Dans toute la suite E est un ensemble fini non vide ayant n éléments et R est une relation binaire définie sur E.

1) a) Quel est le nombre d’éléments de E×E ?
     b) Quel est le nombre d’éléments de P(E×E) ?
     c) Combien peut-on définir de relations binaires sur E ?
     d) Combien peut-on définir de relations binaires réflexives sur E ?
     e) Combien peut-on définir de relations binaires symétriques sur E ?
     f) Question ouverte : Combien peut-on définir de relations binaires transitives sur E ?
2) a) Montrer qu’ils existent deux entiers naturels p et q tels que  et R^p=R^q.
     b) Ce résultat reste-t-il vrai si E est infini ?
3) Soient p et q deux entiers naturels tels que  et R^p=R^q. Posons r=q-p. Montrer que :
     a) R^p+k=R^q+k pour tout kN
     b) R^p+kr+i=R^q+i pour tout kN, i étant un entier naturel quelconque fixé.
     c) R^k{R⁰, R, R², R², R³, … , R^q-1} pour tout kN
4) Déduire de ce qui précède que la fermeture transitive de R est donnée par :
5) a) Montrer que :
     b) Montrer que :
     c) Déduire de ce qui précède que :
     d) Donner un exemple où :  avec m<n.

Application : Reprenons l’exercice I du TD II

E={a, b, c, d, e, f, g, h} désigne un ensemble d’émissions de télévision. Le père, la mère et le fils d’une même famille ont chacun classé ces émissions par ordre de préférence :
         père : a, b, c, d, e, f, g, h
         mère : a, c, f, b, d, e, g, h
         fils : a, b, c, e, f, d, h, g
On se propose d’étudier l’existence d’un ordre de préférence pour l’ensemble de la famille.
On dira que l’émission x est préférée à l’émission y si au moins une personne de la famille préfère x à y. Cette relation R n’est pas transitive (voir TD II exercice I). Convenons qu’elle est réflexive.
1) Donner la matrice booléenne de R.
2) Donner la fermeture transitive  t(R) de R.
3) Donner les propriétés de t(R) et conclure.