In a set of 20 elements there are different subsets of 7 elements such that each of these subsets intersects exactly other subsets. Find the maximum for which this is possible.
The answer is .
In a set of 20 elements there are different subsets of 7 elements such that each of these subsets intersects exactly other subsets. Find the maximum for which this is possible.
The answer is .
Let be the set of residues mod20. An example is given by the sets .
Let . Obviously among any three 7-element subsets there are two intersecting subsets.
Let be any of the subsets. It intersects other subsets . The remaining subsets , do not intersect and are therefore pairwise intersecting. Since each intersects other subsets, it intersects exactly one . This can not be the same for all because can not intersect subsets.
Thus there are two different intersecting different ; let intersect and intersect . All the subsets that do not intersect must intersect each other; there is among them, therefore they are and all . Hence every and , intersect. Applying the same argument to we see that any and , intersect. We see that the family contains only one pair, and , of non-intersecting subsets, while intersects and intersects . For each this list contains subsets intersecting . It follows that no with intersects any , that is, there are no such , and .