Maths Olympiad Prep

Library / /30 of 36

Combinatorics Difficulty 6.3 National Olympiad Prove it Saudi Arabia

Let A1,A2,,A20A_1, A_2, \dots, A_{20} be 20 distinct subsets of size 3 of the set X={1,2,,10}X = \{1, 2, \dots, 10\}. We say that a subset SS of XX is a covering subset if for every 1i201 \le i \le 20, it holds that SAiS \cap A_i \ne \emptyset. What is the minimum possible value of kk, such that there always exists a covering subset of size kk?

Solution

First, we select all the 3-element subsets of X1={1,2,3,4,5}X_1 = \{1, 2, 3, 4, 5\} and of X2={6,7,8,9,10}X_2 = \{6, 7, 8, 9, 10\}. Then, the number of subsets will be (53)+(53)=20\binom{5}{3} + \binom{5}{3} = 20. Suppose there is a covering set of size k5k \le 5, then one of the two sets X1,X2X_1, X_2 will have no more than 2 elements, which means that there are 3 elements belonging to either X1X_1 or X2X_2 that are not selected. Clearly, the given condition is not satisfied. Thus, k6k \ge 6.

We will prove that there always exists a covering set of size 6. We will show that there are 4 numbers a,b,c,dXa, b, c, d \in X of which at most 2 of these 4 numbers are selected into the given subsets. Suppose by contradiction that for every set of 4 numbers taken from XX, there is always a subset of them chosen. We count in two ways the number of connections between the 4 sets of numbers (a,b,c,d)(a, b, c, d) taken from XX and the given subsets.

* Counting by tuple (a,b,c,d)(a, b, c, d): there are at least (104)=210\binom{10}{4} = 210 connections.
* Counting by subsets: each subset of 3 elements will belong to 7 different tuples of 4 numbers, there are 20 subsets are given, so the number of connections is 720=140<2107 \cdot 20 = 140 < 210.

From here we see that there is an absurdity, so there should always be 4 numbers a,b,c,da, b, c, d as stated. At this point, we choose the remaining 6 numbers in XX. Then, each subset of 3 elements in the 20 given sets will always have at least one number belonging to these 6 values. So the minimum value to find is kmin=6k_{\min} = 6. \square

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.