Maths Olympiad Prep

Library / /43 of 52

Combinatorics Difficulty 8.6 Shortlist Prove it Romania

Let nn be an integer greater than 11 and let SS be a finite set containing more than n+1n+1 elements. Consider the collection of all sets A\mathcal{A} of subsets of SS satisfying the following two conditions:
(a) Each member of A\mathcal{A} contains at least nn elements of SS; and
(b) Each element of SS is contained in at least nn members of A\mathcal{A}.
Determine maxAminBB\max_{\mathcal{A}} \min_{\mathcal{B}} |\mathcal{B}|, as B\mathcal{B} runs through all subsets of A\mathcal{A} whose members cover SS, and A\mathcal{A} runs through the above collection.

Solution

The required number is m=Snm = |S| - n. We begin by showing that any set A\mathcal{A} of subsets of SS satisfying the two conditions in the statement has a subcover of cardinality at most mm.

This is clear if SS is a member of A\mathcal{A}.

Assume henceforth that A\mathcal{A} does not contain SS. If some member AA of A\mathcal{A} has more than nn elements, for each element of SAS \setminus A choose a containing member of A\mathcal{A}. The latter along with AA form a subcover of A\mathcal{A} of cardinality SA+1S(n+1)+1=m|S \setminus A| + 1 \le |S| - (n+1) + 1 = m.

Assume henceforth that each member of A\mathcal{A} has exactly nn elements. Fix a member AA of A\mathcal{A}.

If some member BB of A\mathcal{A} contains more than one element of SAS \setminus A, for each element of S(AB)S \setminus (A \cup B) choose a containing member of A\mathcal{A}. The latter along with AA and BB form a subcover of A\mathcal{A} of cardinality S(AB)+2=SA(SA)B+2SA=m|S \setminus (A \cup B)| + 2 = |S \setminus A| - |(S \setminus A) \cap B| + 2 \le |S \setminus A| = m.

Finally, if no member of A\mathcal{A} contains more than one element of SAS \setminus A, write SA={x1,x2,,xm}S \setminus A = \{x_1, x_2, \dots, x_m\}, choose a member A1A_1 of A\mathcal{A} containing x1x_1 and notice that AA1A \setminus A_1 is a singleton set, say AA1={x}A \setminus A_1 = \{x\}. Since x2x_2 is contained in at least nn members of A\mathcal{A}, each of which contains (exactly) n1n-1 elements of AA, we may choose a member A2A_2 of A\mathcal{A} containing both xx and x2x_2 (recall that n2n \ge 2). If n3n \ge 3, continue choosing members AiA_i of A\mathcal{A} containing xix_i, i=3,,ni = 3, \dots, n, to form an mm-element subcover of A\mathcal{A} consisting of A1,A2,,AmA_1, A_2, \dots, A_m.

To complete the proof, we produce a set of subsets of SS satisfying the two conditions in the statement, no subcover of which has less than mm members. To this end, write S={1,2,,m+n}S = \{1, 2, \dots, m+n\}, m2m \ge 2, and let S1,S2,,SnS_1, S_2, \dots, S_n be the (n1)(n-1)-element subsets of the upper part {m+1,m+2,,m+n}\{m+1, m+2, \dots, m+n\} of SS. The sets Si,j=Sj{i}S_{i,j} = S_j \cup \{i\}, i=1,2,,mi = 1, 2, \dots, m, j=1,2,,nj = 1, 2, \dots, n, satisfy both conditions in the statement and at least mm of them are needed to cover SS. (The condition m2m \ge 2 is required for an element in the upper part to lie in at least nn of these 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.