Maths Olympiad Prep

Library / /306 of 520

Combinatorics Difficulty 6.6 National olympiad Find the answer

In a set of 20 elements there are 2k+12 k+1 different subsets of 7 elements such that each of these subsets intersects exactly kk other subsets. Find the maximum kk for which this is possible.

The answer is k=2k=2.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let MM be the set of residues mod20. An example is given by the sets Ai={4i+1,4i+2,4i+3,4i+4,4i+5,4i+6,4i+7}M,i=0,1,2,3,4A_{i}=\{4 i+1,4 i+2,4 i+3,4 i+4,4 i+5,4 i+6,4 i+7\} \subset M, i=0,1,2,3,4.

Let k2k \geq 2. Obviously among any three 7-element subsets there are two intersecting subsets.

Let AA be any of the 2k+12 k+1 subsets. It intersects kk other subsets B1,,BkB_{1}, \ldots, B_{k}. The remaining subsets C1C_{1}, ,Ck\ldots, C_{k} do not intersect AA and are therefore pairwise intersecting. Since each CiC_{i} intersects kk other subsets, it intersects exactly one BjB_{j}. This BjB_{j} can not be the same for all CiC_{i} because BjB_{j} can not intersect k+1k+1 subsets.

Thus there are two different CiC_{i} intersecting different BjB_{j}; let C1C_{1} intersect B1B_{1} and C2C_{2} intersect B2B_{2}. All the subsets that do not intersect C1C_{1} must intersect each other; there is AA among them, therefore they are AA and all Bi,i1B_{i}, i \neq 1. Hence every BjB_{j} and Bj,i1,j1B_{j}, i \neq 1, j \neq 1, intersect. Applying the same argument to C2C_{2} we see that any BiB_{i} and Bj,i2,j2B_{j}, i \neq 2, j \neq 2, intersect. We see that the family A,B1,,BkA, B_{1}, \ldots, B_{k} contains only one pair, B1B_{1} and B2B_{2}, of non-intersecting subsets, while B1B_{1} intersects C1C_{1} and B2B_{2} intersects C2C_{2}. For each ii this list contains kk subsets intersecting BiB_{i}. It follows that no CiC_{i} with i>2i>2 intersects any BjB_{j}, that is, there are no such CiC_{i}, and k2k \leq 2.

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.