Let be a positive integer, and a set with elements. Let be subsets of such that the union of any of them has more than elements.
Prove that among these subsets there exist subsets such that any two of them have a common element.
Solution
1. **Define the Graph **:
- Let be a graph where each vertex represents one of the subsets .
- Draw an edge between two vertices if the corresponding subsets have a common element.
2. **Assume is Triangle-Free**:
- Suppose does not contain any triangles, i.e., there are no three vertices such that each pair of them is connected by an edge.
3. **Degree of Vertices in **:
- We will show that every vertex in has a degree of at most 50.
- Assume for contradiction that there exists a vertex with degree at least 51. Let be adjacent to vertices .
4. Union of Subsets:
- Consider the sets corresponding to . The union of these 51 sets must have more than elements.
- By the Pigeonhole Principle, at least one of these sets, say , must have more than elements.
5. Contradiction:
- Now consider the sets corresponding to . The union of these 50 sets must also have more than elements.
- Since has more than elements, there must be some overlap with the union of .
- Therefore, at least one of must be adjacent to , forming a triangle , which contradicts our assumption that is triangle-free.
6. Existence of Triangles:
- Since cannot be triangle-free, there must be at least one triangle in .
- In fact, there are at least 18 triangles in . Suppose there are at most 17 triangles: where .
- This leaves at least vertices not in these triangles. Call these vertices "free vertices".
7. Degree of Free Vertices:
- A free vertex can have at most degree 50 (otherwise, it would form a triangle with some other vertices).
- Therefore, at least 50 vertices are not connected to , implying .
8. Union of Free Vertices:
- The union of the sets corresponding to these free vertices has less than elements, which contradicts the given condition that the union of any 50 subsets has more than elements.
Thus, we have shown that there must exist at least three subsets among the 101 subsets such that any two of them have a common element.