Exercise 14, § 5

Let E be a finite set with $n$ elements, let $(a_j)_{1 \leqslant j \leqslant n}$ be the sequence of elements of E arranged in some order, and let $(\mathrm{A}_i)_{1 \leqslant i \leqslant m}$ be a sequence of subsets of E.

(a) For each index $j$, let $k_j$ be the number of indices $i$ such that $a_j \in \mathrm{A}_i$, and let $\mathrm{S}_i = \mathrm{Card}\,(\mathrm{A}_i)$. Show that

(b) Suppose that, for each subset $\{x,\, y\}$ of two elements of E, there exists exactly one index $i$ such that $x$ and $y$ are contained in $\mathrm{A}_i$. Show that, if $a_j \notin \mathrm{A}_i$, then $\mathrm{S}_i \leqslant k_j$.

(c) With the hypotheses of (b), show that $m \geqslant n$. (Let $k_n$ be the least of the numbers $k_j$. Show that we may suppose that, whenever $i \leqslant k_n, j \leqslant k_n$, and $i \neq j$, we have $a_j \notin \mathrm{A}_i$ and $a_n \notin \mathrm{A}_j$ for all $j \geqslant k_n$.)

(d) With the hypotheses of (b), show that $m = n$ if and only if one of the following two alternatives is true : (i) $\mathrm{A}_1 = \{a_1,\, a_2,\, \ldots,\, a_{n-1}\}$, $\mathrm{A}_i = \{a_{i-1},\, a_n\}$ for $i = 2, \ldots, n$; (ii) $n = k(k-1) + 1$, each $\mathrm{A}_i$ has $k$ elements, and each element of E belongs to exactly $k$ sets $\mathrm{A}_i$.