Exercices
1 Vraioufaux ?
a) Unep roposition P telleq ue, pour tout n ∈ N,
P(n) ⇒ P(n +1)e st vraie pour tout n ∈ N.
b) Il n’existe aucune injection d’un ensemble de cardinal
200 dans un ensemble de cardinal 100.
c) Toute application d’un ensemble de cardinal 100 dans
un ensemble de cardinal 200 est injective.
d) Toute injection d’un ensemble dans lui-même estbijective.
e) Le cardinal de la réunion de deux ensembles finis est la
sommedeleurs cardinaux.
f) Le cardinal du produitcartésien de deux ensembles finis
est le produitdeleurs cardinaux.
g) A
p
n est le nombre d’injectionsd’un ensemble de cardinal
p dans un ensemble de cardinal n.
h)
n
p
est le nombre de surjections d’un ensemble de
cardinal n dans un ensemble de cardinal p.
i) La somme des termesdela n
e
ligne du triangle de Pascal
est2
n
.
j)
n
p=0
n
p
(−2)
p
= (−1)
n
.
Récurrence
2 Montrerque ∀n ∈ N
∗
2
n−1
n! n
n
.
3 Montrer que ∀n ∈ N
∗
(n +1)!
n
k=1
k!.
4 Montrerque :
1) ∀n ∈ N 3
2n
− 2
n
est divisible par 7.
2) ∀n ∈ N 3
2n+2
+2
6 n +1
est divisible par 11.
3) ∀n 22
2
n − 6e st divisible par 10.
4) La somme des cubes de trois entiers consécutifs est divisible par 9.
5 La suite de Fibonacci est définie par :
u 0 = 1 , u 1 = 1e t∀ n ∈ Nu n +2 = u n+1 + u n
1) Calculer les dix premiers termes de cette suite.
2) Montrer que :
∀n ∈ N u n
5
3
n
Ensembles finis
6 Soit E un ensemble fini et A une partiede E.
Démontrer que, s’il existe une bijection de A dans E,
alors A = E.
Ce résultat est-il vrai si E est infini ?
7 E, F , G étant trois ensembles finis,exprimer :
Card (E ∪ F ∪ G)e nfonction des cardinaux des ensembles
E, F , G, E ∩ F , F ∩ G, E ∩ G et E ∩ F ∩ G.
8 Le service de surveillance d’une centrale nucléaire disposed e n agents ;i lyae np ermanence une équipe de
trois agents en service.D éterminer la valeur maximale de
n pour que l’on puisse repérer une équipe quelconque par
une suite de deux lettres, par exemple ZX, TT ou XZ...
Dénombrements
9 Combien peut-on écrire d’anagrammesdes mots :
MATHS; MOTO ;D ODO ;A NAGRAMME ?
10 Quelle est la probabilité que, dans votre classe,d eux
élèvesa um oins aient leur anniversaire le même jour ?À
partir de quel effectif cette probabilité est-elle supérieure à
50 %?à90%?
11 Une classe comporte 30 élèves. De combien de façons
peut-onconstituer des trinômes de colle ?
Plus généralement, combien existe-t-il de partitions d’un
ensemble de cardinal np en n parties de cardinal p ?
12 Démontrer, de plusieurs façons, que tout ensemble
fini non videpossède autant de parties de cardinal pair que
de parties de cardinal impair.
13 Soit E un ensemble fini de cardinal n.
1) Déterminer le nombre de couples (X , Y ) ∈P(E)
2
tels
que X ⊂ Y .
2) Déterminerlenombre de couples (X , Y ) ∈P(E)
2
tels
que X ∩ Y = ∅.
180
1 Vraioufaux ?
a) Unep roposition P telleq ue, pour tout n ∈ N,
P(n) ⇒ P(n +1)e st vraie pour tout n ∈ N.
b) Il n’existe aucune injection d’un ensemble de cardinal
200 dans un ensemble de cardinal 100.
c) Toute application d’un ensemble de cardinal 100 dans
un ensemble de cardinal 200 est injective.
d) Toute injection d’un ensemble dans lui-même estbijective.
e) Le cardinal de la réunion de deux ensembles finis est la
sommedeleurs cardinaux.
f) Le cardinal du produitcartésien de deux ensembles finis
est le produitdeleurs cardinaux.
g) A
p
n est le nombre d’injectionsd’un ensemble de cardinal
p dans un ensemble de cardinal n.
h)
n
p
est le nombre de surjections d’un ensemble de
cardinal n dans un ensemble de cardinal p.
i) La somme des termesdela n
e
ligne du triangle de Pascal
est2
n
.
j)
n
p=0
n
p
(−2)
p
= (−1)
n
.
Récurrence
2 Montrerque ∀n ∈ N
∗
2
n−1
n! n
n
.
3 Montrer que ∀n ∈ N
∗
(n +1)!
n
k=1
k!.
4 Montrerque :
1) ∀n ∈ N 3
2n
− 2
n
est divisible par 7.
2) ∀n ∈ N 3
2n+2
+2
6 n +1
est divisible par 11.
3) ∀n 22
2
n − 6e st divisible par 10.
4) La somme des cubes de trois entiers consécutifs est divisible par 9.
5 La suite de Fibonacci est définie par :
u 0 = 1 , u 1 = 1e t∀ n ∈ Nu n +2 = u n+1 + u n
1) Calculer les dix premiers termes de cette suite.
2) Montrer que :
∀n ∈ N u n
5
3
n
Ensembles finis
6 Soit E un ensemble fini et A une partiede E.
Démontrer que, s’il existe une bijection de A dans E,
alors A = E.
Ce résultat est-il vrai si E est infini ?
7 E, F , G étant trois ensembles finis,exprimer :
Card (E ∪ F ∪ G)e nfonction des cardinaux des ensembles
E, F , G, E ∩ F , F ∩ G, E ∩ G et E ∩ F ∩ G.
8 Le service de surveillance d’une centrale nucléaire disposed e n agents ;i lyae np ermanence une équipe de
trois agents en service.D éterminer la valeur maximale de
n pour que l’on puisse repérer une équipe quelconque par
une suite de deux lettres, par exemple ZX, TT ou XZ...
Dénombrements
9 Combien peut-on écrire d’anagrammesdes mots :
MATHS; MOTO ;D ODO ;A NAGRAMME ?
10 Quelle est la probabilité que, dans votre classe,d eux
élèvesa um oins aient leur anniversaire le même jour ?À
partir de quel effectif cette probabilité est-elle supérieure à
50 %?à90%?
11 Une classe comporte 30 élèves. De combien de façons
peut-onconstituer des trinômes de colle ?
Plus généralement, combien existe-t-il de partitions d’un
ensemble de cardinal np en n parties de cardinal p ?
12 Démontrer, de plusieurs façons, que tout ensemble
fini non videpossède autant de parties de cardinal pair que
de parties de cardinal impair.
13 Soit E un ensemble fini de cardinal n.
1) Déterminer le nombre de couples (X , Y ) ∈P(E)
2
tels
que X ⊂ Y .
2) Déterminerlenombre de couples (X , Y ) ∈P(E)
2
tels
que X ∩ Y = ∅.
180