COURS 9
Nombresentiers naturels –Combinatoire
Exemples : 1) Id [[ 1 , n ]] est bijective, donc [[ 1 , n ]] est fini et son cardinal est n.
2) Si m et n sont deux entiers naturels tels que m n, montrer que l’ensemble
[[ m , n ]] = { p ∈ N , m p n } est fini et trouver son cardinal.
3) Montrer que toute partie I de [[ 1 , n ]] est finie, et que son cardinal estinférieur
ou égal à n. (Si I n’estpas vide, il aunplus petit élément que l’on peut appeler
f (1) ;c ontinuer...)
Le théorème 2 s’étend aux ensembles finis :
Corollaire 2.1
Soit E et F deux ensembles finis.
1) Il existe une injection de E dans F
⇐⇒
Card E Card F .
2) Il existe une surjection de E dans F
⇐⇒
Card E Card F .
3) Il existe une bijection de E dans F
⇐⇒
Card E = Card F .
4) Si Card E = Card F
= 0, toute injection de E dans F estbijective.
5) Si Card E = Card F , toutesurjection de E dans F est bijective.
Pours’entraîner :ex. 6
APPLICATION 4
Principe des tiroirs
Une application d’un ensemble fini dans un autre dont le
cardinal est strictement inférieur au premier ne peut pas
être injective :ilexiste donc nécessairement deux éléments
qui ontlamême image. C’est ce qu’on appelle familièrement le principe des tiroirs :sionrangepobjetsdans
nt iroirs et quen qui sont dans le même tiroir... Sous son aird ’évidence,
ce principe permet de démontrer des propriétés qui ne le
sont pastoujours.
Premier exemple :Deux pays sont dits voisins s’ils ont
une frontière commune. Démontrerq u’il existe nécessairementd eux pays qui ont le même nombre de
voisins.
Soit n le nombre totaldepays. Le nombre de voisins
d’un pays varie de 0àn − 1 .Mais, s’il existe un pays
sans voisin (une île), alors aucun pays n’a n − 1v oisins.P ar conséquent, le nombre de voisins d’un pays
ne peut prendre au plus que n − 1v aleurs. L’application qui, àu np ays, associe son nombre de voisins
n’est doncpas injective.
Second exemple :Soit E un ensemble de 10 nombres
entiersd istincts compris entre 1e t1 00. Démontrer
qu’il existe deux sous-ensembles de E non vides et
disjointsayant la même somme.
Remarquons tout d’abordqu’il suffit de trouver deux
sous-ensembles distincts non vides de même somme ;
en leur retranchant leur intersection,i lr estera deux
sous-ensembles disjoints de même somme, qui ne sauraient être vides.
Le nombre de sous-ensembles nonv ides de E est
2
10
− 1 = 1023. La sommed es éléments d’un tel
sous-ensemble est au moins égaleà1,et, au plus, égale
à9 1+92 + ··· +100 = 955 . Il yadonc plus de
sous-ensembles non vides que de sommes possibles.
170
Nombresentiers naturels –Combinatoire
Exemples : 1) Id [[ 1 , n ]] est bijective, donc [[ 1 , n ]] est fini et son cardinal est n.
2) Si m et n sont deux entiers naturels tels que m n, montrer que l’ensemble
[[ m , n ]] = { p ∈ N , m p n } est fini et trouver son cardinal.
3) Montrer que toute partie I de [[ 1 , n ]] est finie, et que son cardinal estinférieur
ou égal à n. (Si I n’estpas vide, il aunplus petit élément que l’on peut appeler
f (1) ;c ontinuer...)
Le théorème 2 s’étend aux ensembles finis :
Corollaire 2.1
Soit E et F deux ensembles finis.
1) Il existe une injection de E dans F
⇐⇒
Card E Card F .
2) Il existe une surjection de E dans F
⇐⇒
Card E Card F .
3) Il existe une bijection de E dans F
⇐⇒
Card E = Card F .
4) Si Card E = Card F
= 0, toute injection de E dans F estbijective.
5) Si Card E = Card F , toutesurjection de E dans F est bijective.
Pours’entraîner :ex. 6
APPLICATION 4
Principe des tiroirs
Une application d’un ensemble fini dans un autre dont le
cardinal est strictement inférieur au premier ne peut pas
être injective :ilexiste donc nécessairement deux éléments
qui ontlamême image. C’est ce qu’on appelle familièrement le principe des tiroirs :sionrangepobjetsdans
nt iroirs et quen qui sont dans le même tiroir... Sous son aird ’évidence,
ce principe permet de démontrer des propriétés qui ne le
sont pastoujours.
Premier exemple :Deux pays sont dits voisins s’ils ont
une frontière commune. Démontrerq u’il existe nécessairementd eux pays qui ont le même nombre de
voisins.
Soit n le nombre totaldepays. Le nombre de voisins
d’un pays varie de 0àn − 1 .Mais, s’il existe un pays
sans voisin (une île), alors aucun pays n’a n − 1v oisins.P ar conséquent, le nombre de voisins d’un pays
ne peut prendre au plus que n − 1v aleurs. L’application qui, àu np ays, associe son nombre de voisins
n’est doncpas injective.
Second exemple :Soit E un ensemble de 10 nombres
entiersd istincts compris entre 1e t1 00. Démontrer
qu’il existe deux sous-ensembles de E non vides et
disjointsayant la même somme.
Remarquons tout d’abordqu’il suffit de trouver deux
sous-ensembles distincts non vides de même somme ;
en leur retranchant leur intersection,i lr estera deux
sous-ensembles disjoints de même somme, qui ne sauraient être vides.
Le nombre de sous-ensembles nonv ides de E est
2
10
− 1 = 1023. La sommed es éléments d’un tel
sous-ensemble est au moins égaleà1,et, au plus, égale
à9 1+92 + ··· +100 = 955 . Il yadonc plus de
sous-ensembles non vides que de sommes possibles.
170