Combinatoire B
12 Février
On corrigera en priorité les exercices 1, 4, 5, 7, 9, 11, 12, 14, et d’autres s’il reste du temps.
Exercice 1.
Combien d’enfants faut-il au minimum dans une école pour que l’on soit sûr que 3 d’entre eux
au moins aient leur anniversaire le même jour ? (on considère aussi le 29 février)
Exercice 2.
On considère un groupe de n personnes (n > 1), dans lequel certaines personnes se serrent la
main.
Prouver qu’il existe au moins deux personnes ayant donné le même nombre de poignées de
main.
Exercice 3.
On colorie le plan de deux couleurs différentes, montrer qu’il existe deux points de la même
couleur à un mètre de distance.
Exercice 4.
On considère
√ 5 points dans un carré de côté 2, montrer qu’il y en a deux qui sont à distance au
plus 2 l’un de l’autre.
Exercice 5.
Combien d’entiers au minimum doit-on sélectionner dans l’ensemble {1, 2, . . . , 20} pour être sûr
que parmi ceux-ci on ait deux entiers a et b tels que a − b = 2 ?
Exercice 6.
On considère S une partie de l’ensemble des parties de {1, 2, . . . n}, telle que deux éléments de S
ne soient jamais disjoints.
Montrer que S est de cardinal au plus 2n−1 .
Montrer que cette borne est atteinte.
Exercice 7.
Soient a1 , . . . an des entiers relatifs pas forcément distincts, montrer qu’il existe 0 ⩽ k < l ⩽ n
tels que la somme ak+1 + . . . al soit divisible par n.
1
Exercice 8.
Sur un tableau sont écrits 20 nombres distincts entre 1 et 64. Sur un autre tableau sont écrites
toutes les différences (non nulles, sinon ça n’a pas d’intérêt) qu’on puisse calculer avec ces
nombres. Montrer qu’un nombre est écrit quatre fois sur ce deuxième tableau.
Exercice 9.
On choisit dix entiers quelconques à 2 chiffres. Montrer que parmi eux, on peut trouver deux
sous-ensembles disjoints de même somme.
Exercice 10.
Simplifier le rapport
n
k
n .
k+1
2n 2n 2n
En déduire que pour tout k, ⩽ , puis une minoration de .
k n n
2n 4n
Remarque : on peut en fait montrer que ≈√ .
n nπ
Exercice 11.
Montrer que
n n+1 r r+1
+ + ··· + = .
n n n n+1
Indice : Dessiner le triangle de Pascal.
Exercice 12.
Parmi les entiers plus petits que 10000, combien sont ni multiples de 3, ni de 5, ni de 7 ?
Exercice 13. (Morphisme de Frobenius)
p
1)Soit p un nombre premier, montrer que est divisible par p pour 1 ⩽ k ⩽ p − 1.
k
2) Montrer que (x + y)p ≡ xp + yp (mod p).
Exercice 14. (Identité de Vandermonde)
En développant l’expression (1 + x)m+n = (1 + x)m (1 + x)n de deux manières différentes, mon-
trer que si 0 ⩽ r ⩽ m + n, on a
m+n n m n m n m n m
= + + ··· + + .
r 0 r 1 r−1 r−1 1 r 0
En déduire la valeur de
2 2 2 2 2
n n n n n
+ + + ··· + + .
0 1 2 n−1 n
