Maths Olympiad Prep

Library / /2 of 2

Combinatorics Difficulty 7.8 National olympiad, round 2 Prove it Romania

Let nn be an integer greater than 11 and let XX be an nn-element set. A non-empty collection of subsets A1,,AkA_1, \dots, A_k of XX is tight if the union A1AkA_1 \cup \dots \cup A_k is a proper subset of XX and no element of XX lies in exactly one of the AiA_is. Find the largest cardinality of a collection of proper non-empty subsets of XX, no non-empty subcollection of which is tight.

Solution

Note. A subset AA of XX is proper if AXA \ne X. The sets in a collection are assumed to be distinct. The whole collection is assumed to be a subcollection.

First solution. (Ilya Bogdanov) The required maximum is 2n22n-2. To describe a (2n2)(2n-2)-element collection satisfying the required conditions, write X={1,2,,n}X = \{1, 2, \dots, n\} and set Bk={1,2,,k}B_k = \{1, 2, \dots, k\}, k=1,2,,n1k = 1, 2, \dots, n-1, and Bk={kn+2,kn+3,,n}B_k = \{k-n+2, k-n+3, \dots, n\}, k=n,n+1,,2n2k=n, n+1, \dots, 2n-2. To show that no subcollection of the BkB_k is tight, consider a subcollection CC whose union UU is a proper subset of XX, let mm be an element in XUX \setminus U, and notice that CC is a subcollection of {B1,,Bm1,Bm+n1,,B2n2}\{B_1, \dots, B_{m-1}, B_{m+n-1}, \dots, B_{2n-2}\}, since the other BB's are precisely those containing mm. If UU contains elements less than mm, let kk be the greatest such and notice that BkB_k is the only member of CC containing kk; and if UU contains elements greater than mm, let kk be the least such and notice that Bk+n2B_{k+n-2} is the only member of CC containing kk. Consequently, CC is not tight.

We now proceed to show by induction on n2n \ge 2 that the cardinality of a collection of proper non-empty subsets of XX, no subcollection of which is tight, does not exceed 2n22n-2. The base case n=2n=2 is clear, so let n>2n > 2 and suppose, if possible, that B\mathcal{B} is a collection of 2n12n-1 proper non-empty subsets of XX containing no tight subcollection.
To begin, notice that B\mathcal{B} has an empty intersection: if the members of B\mathcal{B} shared an element xx, then B={B{x}:BB,B{x}}\mathcal{B}' = \{B \setminus \{x\} : B \in \mathcal{B}, B \ne \{x\}\} would be a collection of at least 2n22n-2 proper non-empty subsets of X{x}X \setminus \{x\} containing no tight subcollection, and the induction hypothesis would be contradicted.
Now, for every xx in XX, let BxB_x be the (non-empty) collection of all members of B\mathcal{B} not containing xx. Since no subcollection of B\mathcal{B} is tight, BxB_x is not tight, and since the union of BxB_x does not contain xx, some xx' in XX is covered by a single member of BxB_x. In other words, there is a single set in B\mathcal{B} covering xx' but not xx. In this case, draw an arrow from xx to xx'. Since there is at least one arrow from each xx in XX, some of these arrows form a (minimal) cycle x1x2xkxk+1=x1x_1 \to x_2 \to \dots \to x_k \to x_{k+1} = x_1 for some suitable integer k2k \ge 2. Let AiA_i be the unique member of B\mathcal{B} containing xi+1x_{i+1} but not xix_i, and let X={x1,x2,,xk}X' = \{x_1, x_2, \dots, x_k\}.
Remove A1,A2,,AkA_1, A_2, \dots, A_k from B\mathcal{B} to obtain a collection B\mathcal{B}' each member of which either contains or is disjoint from XX': for if a member BB of B\mathcal{B}' contained some but not all elements of XX', then BB should contain xi+1x_{i+1} but not xix_i for some ii, and B=AiB = A_i, a contradiction. This rules out the case k=nk=n, for otherwise B={A1,A2,,An}B = \{A_1, A_2, \dots, A_n\}, so B<2n1|B| < 2n-1.
To rule out the case k<nk < n, consider an extra element xx^* outside XX and let
B={B:BB,BX=}{(BX){x}:BB,XB}; B^* = \{B: B \in B', B \cap X' = \emptyset\} \cup \{(B \setminus X') \cup \{x^*\}: B \in B', X' \subseteq B\};
thus, in each member of BB' containing XX', the latter is collapsed to singleton xx^*. Notice that BB^* is a collection of proper non-empty subsets of X=(XX){x}X^* = (X \setminus X') \cup \{x^*\}, no subcollection of which is tight. By the induction hypothesis, B=B2X2=2(nk)|B'| = |B^*| \le 2|X^*| - 2 = 2(n-k), so B2(nk)+k=2nk<2n1|B| \le 2(n-k)+k = 2n-k < 2n-1, a final contradiction.

Second solution. Proceed again by induction on nn to show that the cardinality of a collection of proper non-empty subsets of XX, no subcollection of which is tight, does not exceed 2n22n-2.
Consider any collection B\mathcal{B} of proper non-empty subsets of XX with no tight subcollection; call such a collection good. Assume that there exist M,NBM, N \in \mathcal{B} such that MNM \cup N is distinct from M,NM, N, and XX. In this case, we will show how to modify B\mathcal{B} so that it remains good, contains the same number of sets, but the total number of elements in the sets of B\mathcal{B} increases.
Consider a maximal (relative to set-theoretic inclusion) subcollection CBC \subseteq \mathcal{B} such that the set C=CCCC = \bigcup_{C' \in C} C' is distinct from XX and from all members of CC. Notice here that the union of any subcollection DBD \subset \mathcal{B} cannot coincide with any KBDK \in \mathcal{B} \setminus D, otherwise {K}D\{K\} \cup D would be tight. Surely, CC exists (since {M,N}\{M, N\} is an example of a collection satisfying the requirements on CC, except for maximality); moreover, CBC \notin \mathcal{B} by the above remark.
Since CXC \ne X, there exists an LCL \in C and xLx \in L such that LL is the unique set in CC containing xx. Now replace in B\mathcal{B} the set LL by CC in order to obtain a new collection B\mathcal{B}' (then B=B|\mathcal{B}'| = |\mathcal{B}|). We claim that B\mathcal{B}' is good.
Assume, to the contrary, that B\mathcal{B}' contained a tight subcollection T\mathcal{T}; clearly, CTC \in \mathcal{T}, otherwise B\mathcal{B} is not good. If TC{C}\mathcal{T} \subseteq C \cup \{C\}, then CC is the unique set in T\mathcal{T} containing xx which is impossible. Therefore, there exists PT(C{C})P \in \mathcal{T} \setminus (C \cup \{C\}). By maximality of CC, the collection C{P}C \cup \{P\} does not satisfy the requirements imposed on CC; since PCXP \cup C \ne X, this may happen only if CPC \subset P. But then D=(T{C})C\mathcal{D} = (\mathcal{T} \setminus \{C\}) \cup C is a tight subcollection in B\mathcal{B}: all elements of CC are covered by D\mathcal{D} at least twice (by PP).

and an element of C\mathcal{C}), and D\mathcal{D} and T\mathcal{T} both cover all other elements the same number of times – a contradiction. Thus B\mathcal{B}' is good.
Such modifications may be performed finitely many times, since the total number of elements of sets in B\mathcal{B} increases. Thus, at some moment we arrive at a good collection B\mathcal{B} to which the procedure no longer applies. This means that for every M,NBM, N \in \mathcal{B}, either MN=XM \cup N = X or one of them is contained in the other.
Now let MM be a \subseteq-minimal set in B\mathcal{B}. Then each set in B\mathcal{B} either contains MM or forms XX in union with MM (i.e., contains XMX \setminus M). Now one may easily see that the collections
B+={AM:AB,MA,AM}, \mathcal{B}_+ = \{A \setminus M : A \in \mathcal{B}, M \subset A, A \ne M\},
B={AM:AB,XMA,AXM} \mathcal{B}_- = \{A \cap M : A \in \mathcal{B}, X \setminus M \subset A, A \ne X \setminus M\}
are both good as collections of subsets of XMX \setminus M and MM, respectively; thus, by the induction hypothesis, B++B2n4|\mathcal{B}_+| + |\mathcal{B}_-| \le 2n - 4.
Finally, each set ABA \in \mathcal{B} either produces a set in one of the two new collections, or coincides with MM or XMX \setminus M. Thus BB++B+22n2|\mathcal{B}| \le |\mathcal{B}_+| + |\mathcal{B}_-| + 2 \le 2n - 2, as required.

Third solution. We provide yet another proof of the estimate B2n2|\mathcal{B}| \le 2n - 2. Recall the notion of a good collection from Solution 2. Consider any good collection B\mathcal{B}, and for every xXx \in X let Bx={B:BB,xB}\mathcal{B}_x = \{B : B \in \mathcal{B}, x \notin B\}, as in Solution 1.
Consider an element xXx \in X such that Bx|\mathcal{B}_x| is maximal. Since the collection Bx\mathcal{B}_x is not tight, and the union of its members does not contain xx, there exists an element yXy \in X belonging to a unique member of Bx\mathcal{B}_x, say, BB. Thus, Bx{B}By\mathcal{B}_x \setminus \{B\} \subset \mathcal{B}_y.
Since ByBx|\mathcal{B}_y| \le |\mathcal{B}_x| by maximality of the latter, the collection C=ByBx\mathcal{C} = \mathcal{B}_y \setminus \mathcal{B}_x contains at most one member. Set now B=B(C{B})\mathcal{B}' = \mathcal{B} \setminus (\mathcal{C} \cup \{B\}). By the argument above, each set in B\mathcal{B}' contains either both xx and yy, or none of them. Collapse {x,y}\{x, y\} to a singleton xx^* to get a new collection of BB2|\mathcal{B}'| \ge |\mathcal{B}| - 2 subsets of (X{x,y}){x}(X \setminus \{x, y\}) \cup \{x^*\} containing no tight subcollection. By the induction hypothesis B2(n1)2|\mathcal{B}'| \le 2(n-1) - 2, so B2n2|\mathcal{B}| \le 2n - 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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.