Bài tập 14, § 5

Cho E là một tập hợp hữu hạn có $n$ phần tử, $(a_j)_{1 \leqslant j \leqslant n}$ là dãy các phần tử của E được sắp theo một thứ tự nào đó, và $(\mathrm{A}_i)_{1 \leqslant i \leqslant m}$ là một dãy các tập con của E.

(a) Với mỗi chỉ số $j$, gọi $k_j$ là số các chỉ số $i$ sao cho $a_j \in \mathrm{A}_i$, và đặt $\mathrm{S}_i = \mathrm{Card}\,(\mathrm{A}_i)$. Chứng minh rằng

(b) Giả sử rằng, đối với mỗi tập con $\{x,\, y\}$ gồm hai phần tử của E, tồn tại đúng một chỉ số $i$ sao cho $x$ và $y$ được chứa trong $\mathrm{A}_i$. Chứng minh rằng, nếu $a_j \notin \mathrm{A}_i$, thì $\mathrm{S}_i \leqslant k_j$.

(c) Với các giả thiết của (b), chứng minh rằng $m \geqslant n$. (Gọi $k_n$ là số nhỏ nhất trong các số $k_j$. Chứng minh rằng ta có thể giả sử rằng, mỗi khi $i \leqslant k_n, j \leqslant k_n$, và $i \neq j$, thì $a_j \notin \mathrm{A}_i$ và $a_n \notin \mathrm{A}_j$ với mọi $j \geqslant k_n$.)

(d) Với các giả thiết của (b), hãy chứng minh rằng $m = n$ khi và chỉ khi một trong hai khả năng sau đây đúng : (i) $\mathrm{A}_1 = \{a_1,\, a_2,\, \ldots,\, a_{n-1}\}$, $\mathrm{A}_i = \{a_{i-1},\, a_n\}$ với $i = 2, \ldots, n$; (ii) $n = k(k-1) + 1$, mỗi $\mathrm{A}_i$ có $k$ phần tử, và mỗi phần tử của E thuộc đúng $k$ tập hợp $\mathrm{A}_i$.