Maths Olympiad Prep

Library / /83 of 299

Combinatorics Difficulty 6.1 National Olympiad Prove it Iran

A family of some three-element subsets of a 10001000-element set is considered. We know that the union of every 55 of the subsets has at least 1212 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 44 elements. Otherwise, the union of 55 subsets of this connected component has at most 11=3+2+2+2+211 = 3 + 2 + 2 + 2 + 2 elements, which contradicts the assumption of the problem.

Now we show that the number of elements in a connected component is at least 94\frac{9}{4} 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 99 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 77 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 nn subsets, then we have 94n1000\frac{9}{4}n \le 1000 and therefore we have at most 444444 selected subsets.

Now, we will provide an example for 444444 subsets. The sets {9k,9k+1,9k+2}\{9k, 9k+1, 9k+2\}, {9k+2,9k+3,9k+4}\{9k+2, 9k+3, 9k+4\}, {9k+4,9k+5,9k+6}\{9k+4, 9k+5, 9k+6\}, {9k+6,9k+7,9k+8}\{9k+6, 9k+7, 9k+8\} are an example of such sets. ■

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.