A family of some three-element subsets of a -element set is considered. We know that the union of every of the subsets has at least elements. Find the largest possible value for the number of these subsets.
Solution
Consider the selected subsets as vertices of a graph and connect two subsets if they have a common element. We claim that each connected component has at most elements. Otherwise, the union of subsets of this connected component has at most elements, which contradicts the assumption of the problem.
Now we show that the number of elements in a connected component is at least times the number of elements in that connected component. In doing so, we consider several different cases:
If this connected component has four elements, consider the union of these four elements along with an arbitrary element of another connected component. The assumption of the problem implies that the union of these four elements must have at least elements.
If a connected component has three elements, consider the union of these three elements along with two elements of another connected component. Since the union of a connected component has at most five elements, this union must have at least elements.
Similarly, if a connected component has two elements, consider the union of these two elements along with three elements of another connected component. Thus, our claim is proved.
Now since the unions of different connected components are distinct, if we have selected subsets, then we have and therefore we have at most selected subsets.
Now, we will provide an example for subsets. The sets , , , are an example of such sets. ■