Maths Olympiad Prep

Library / /356 of 520

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it

Let n2n\geq 2 be a positive integer, and XX a set with nn elements. Let A1,A2,,A101A_{1},A_{2},\ldots,A_{101} be subsets of XX such that the union of any 5050 of them has more than 5051n\frac{50}{51}n elements.

Prove that among these 101101 subsets there exist 33 subsets such that any two of them have a common element.

Solution

1. **Define the Graph G G **:
- Let G G be a graph where each vertex represents one of the subsets A1,A2,,A101 A_1, A_2, \ldots, A_{101} .
- Draw an edge between two vertices if the corresponding subsets have a common element.

2. **Assume G G is Triangle-Free**:
- Suppose G G 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 G G **:
- We will show that every vertex in G G has a degree of at most 50.
- Assume for contradiction that there exists a vertex v v with degree at least 51. Let v v be adjacent to vertices v1,v2,,v51 v_1, v_2, \ldots, v_{51} .

4. Union of Subsets:
- Consider the sets corresponding to v1,v2,,v51 v_1, v_2, \ldots, v_{51} . The union of these 51 sets must have more than 5051n \frac{50}{51}n elements.
- By the Pigeonhole Principle, at least one of these sets, say Av51 A_{v_{51}} , must have more than n51 \frac{n}{51} elements.

5. Contradiction:
- Now consider the sets corresponding to v1,v2,,v50 v_1, v_2, \ldots, v_{50} . The union of these 50 sets must also have more than 5051n \frac{50}{51}n elements.
- Since Av51 A_{v_{51}} has more than n51 \frac{n}{51} elements, there must be some overlap with the union of Av1,Av2,,Av50 A_{v_1}, A_{v_2}, \ldots, A_{v_{50}} .
- Therefore, at least one of v1,v2,,v50 v_1, v_2, \ldots, v_{50} must be adjacent to v51 v_{51} , forming a triangle vv1v51 vv_1v_{51} , which contradicts our assumption that G G is triangle-free.

6. Existence of Triangles:
- Since G G cannot be triangle-free, there must be at least one triangle in G G .
- In fact, there are at least 18 triangles in G G . Suppose there are at most 17 triangles: a1b1c1,a2b2c2,,akbkck a_1b_1c_1, a_2b_2c_2, \ldots, a_kb_kc_k where k17 k \leq 17 .
- This leaves at least 101317=50 101 - 3 \cdot 17 = 50 vertices not in these triangles. Call these vertices "free vertices".

7. Degree of Free Vertices:
- A free vertex v v 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 v v , implying v<n51 |v| < \frac{n}{51} .

8. Union of Free Vertices:
- The union of the sets corresponding to these free vertices has less than 5051n \frac{50}{51}n elements, which contradicts the given condition that the union of any 50 subsets has more than 5051n \frac{50}{51}n 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.

\blacksquare

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.