Exercice 14, § 5

Soient E un ensemble fini à n éléments, $(a_j)_{1 \leq j \leq n}$ la suite des éléments de E rangés dans un certain ordre, $(A_i)_{1 \leq i \leq m}$ une suite de parties de E. a) Pour tout indice $j$, soit $k_j$ le nombre des indices $i$ tels que $a_j \in A_i$; pour tout indice $i$, soit $s_i = \mathrm{Card}(A_i)$. Montrer que $\sum_{j=1}^n k_j = \sum_{i=1}^m s_i$. b) On suppose que pour toute partie $\{x, y\}$ à deux éléments de E, il existe un indice $i$ et un seul tel que $x$ et $y$ soient contenus dans $A_i$. Montrer que si $a_j \notin A_i$, on a $s_i \leq k_j$. c) Sous les hypothèses de b), montrer que l’on a $m \geq n$. (Soit $k_n$ le plus petit des nombres $k_j$; montrer qu’on peut supposer que, pour $i \leq k_n, j \leq k_n$ et $i \neq j$, on a $a_j \notin A_i$, et $a_n \notin A_j$ pour tout $j > k_n$.) d) Sous les hypothèses de b), montrer que pour que l’on ait $m = n$, il faut et il suffit que l’on soit dans l’un des deux cas suivants: $1^\circ$ $A_1 = \{a_1, a_2, \ldots, a_{n-1}\}$, $A_i = \{a_{i-1}, a_n\}$ pour $2 \leq i \leq n$; $2^\circ$ $n = k(k-1) + 1$, tout $A_i$ est un ensemble à $k$ éléments, et tout élément de E appartient exactement à $k$ ensembles $A_i$.