Let be 20 distinct subsets of size 3 of the set . We say that a subset of is a covering subset if for every , it holds that . What is the minimum possible value of , such that there always exists a covering subset of size ?
Solution
First, we select all the 3-element subsets of and of . Then, the number of subsets will be . Suppose there is a covering set of size , then one of the two sets will have no more than 2 elements, which means that there are 3 elements belonging to either or that are not selected. Clearly, the given condition is not satisfied. Thus, .
We will prove that there always exists a covering set of size 6. We will show that there are 4 numbers 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 , there is always a subset of them chosen. We count in two ways the number of connections between the 4 sets of numbers taken from and the given subsets.
* Counting by tuple : there are at least 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 .
From here we see that there is an absurdity, so there should always be 4 numbers as stated. At this point, we choose the remaining 6 numbers in . 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 .