Example 2 Suppose in Example 1, the maximum number of elements is . Prove:
Solution
First, estimate the upper bound of , i.e., prove the right inequality in (2).
Each three-element subset contains three two-element subsets , , .
Since every two elements (three-element subsets of ) in have at most one common element, the two-element subsets contained in each pair of three-element subsets are all different.
The two-element subsets of total , so
i.e.,
To estimate the lower bound of , the construction method should be used. Construct a batch of three-element subsets, the number of which is , and each pair of them has at most one common element.
For this purpose, consider all three-element subsets that satisfy the condition
(i.e., is divisible by ).
If , and
then
When , (4) is . Therefore, every two (different) three-element subsets that satisfy (3) have at most one common element.
Now, calculate the number of three-element subsets that satisfy (3).
First, choose , which has choices. After is chosen, choose , and does not satisfy the congruence equation
(i.e., when , ; when , ) and
(i.e., . Therefore, has at least choices. After and are determined, is also determined by (3), and is different from and . Therefore, . Thus, the other half of (2) holds.