uniolympiads Ελληνικά

IMC 2016, Day 1, Problem 4

Let n≥kn \ge k be positive integers, and let F\mathcal{F} be a family of finite sets with the following properties:

(i) F\mathcal{F} contains at least (nk)+1\binom{n}{k} + 1 distinct sets containing exactly kk elements;

(ii) for any two sets A,B∈FA, B \in \mathcal{F}, their union A∪BA \cup B also belongs to F\mathcal{F}.

Prove that F\mathcal{F} contains at least three sets with at least nn elements.

Original from the official PDFLet n ≥ k be positive integers, and let F be a family of nite sets with the following properties: (i) F contains at least nk + 1 distinct sets containing exactly k elements; (ii) for any two sets A, B ∈ F , their union A ∪ B also belongs to F . Prove that F contains at least three sets with at least n elements.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(Proposed by Fedor Petrov, St. Petersburg State University)

Solution 1. If n=kn = k then we have at least two distinct sets in the family with exactly nn elements and their union, so the statement is true. From now on we assume that n>kn > k.

Fix (nk)+1\binom{n}{k} + 1 sets of size kk in F\mathcal{F}, call them 'generators'. Let V∈FV\in\mathcal{F} be the union of the generators. Since VV has at least (nk)+1\binom{n}{k} + 1 subsets of size kk, we have ∣V∣>n|V| > n.

Call an element v∈Vv\in V 'appropriate' if vv belongs to at most (n−1k−1)\binom{n-1}{k-1} generators. Then there exist at least (nk)+1−(n−1k−1)=(n−1k)+1\binom{n}{k} + 1 - \binom{n-1}{k-1} = \binom{n-1}{k} + 1 generators not containing vv. Their union contains at least nn elements, and the union does not contain vv.

Now we claim that among any nn elements x1,…,xnx_1,\ldots,x_n of VV, there exists an appropriate element. Consider all pairs (G,xi)(G,x_i) such that GG is a generator and xi∈Gx_i\in G. Every generator has exactly kk elements, so the number of such pairs is at most ((nk)+1)⋅k\big(\binom{n}{k} + 1\big)\cdot k. If some xix_i is not appropriate then xix_i is contained in at least (n−1k−1)+1\binom{n-1}{k-1} + 1 generators; if none of x1,…,xnx_1,\ldots,x_n was appropriate then we wold have at least n⋅((n−1k−1)+1)n\cdot\big(\binom{n-1}{k-1} + 1\big) pairs. But n⋅((n−1k−1)+1)>((n−1k−1)+1)⋅kn\cdot\big(\binom{n-1}{k-1} + 1\big) > (\binom{n-1}{k-1} + 1)\cdot k, so this is not possible; at least one of x1,…,xnx_1,\ldots,x_n must be appropriate.

Since ∣V∣>n|V| > n, the set VV contains some appropriate element v1v_1. Let U1∈FU_1\in\mathcal{F} be the union of all generators not containing v1v_1. Then ∣U1∣≥n|U_1|\ge n and v1∉U1v_1\notin U_1. Now take an appropriate element v2v_2 from U1U_1 and let U2∈FU_2\in\mathcal{F} be the union of all generators not containing v2v_2. Then ∣U2∣≥n|U_2|\ge n, so we have three sets, VV, U1U_1 and U2U_2 in ∈F\in\mathcal{F} with at least nn elements: V≠U1V\ne U_1 because v1∈Vv_1\in V and v1∉U1v_1\notin U_1, and U2U_2 is different from VV and U1U_1 because v2∈V,U1v_2\in V,U_1 but v2∉U2v_2\notin U_2.

Solution 2. We proceed by induction on kk, so we can assume that the statement of the problem is known for smaller values of kk. By contradiction, assume that F\mathcal{F} has less than 33 sets with at least nn elements, that is the number of such sets is 00, 11 or 22. We can assume without loss of generality that F\mathcal{F} consists of exactly N:=(nk)+1N := \binom{n}{k} + 1 distinct sets of size kk and all their possible unions. Denote the sets of size kk by S1,S2,…S_1,S_2,\ldots.

Consider a maximal set I⊂{1,…,N}I\subset\{1,\ldots,N\} such that A:=⋃i∈ISiA := \bigcup_{i\in I} S_i has size less than nn, ∣A∣<n|A| < n. This means that adding any SjS_j for j∉Ij\notin I makes the size at least nn, ∣Sj∪A∣≥n|S_j\cup A|\ge n. First, let's prove that such jj exist. Otherwise, all the sets SiS_i are contained in AA. But there are only (∣A∣k)≤(n−1k)<N\binom{|A|}{k}\le\binom{n-1}{k} < N distinct kk-element subsets of AA, this is a contradiction. So there is at least one jj such that ∣Sj∪A∣≥n|S_j\cup A|\ge n. Consider all possible sets that can be obtained as Sj∪AS_j\cup A for j∉Ij\notin I. Their size is at least nn, so their number can be 11 or 22. If there are two of them, say BB and CC then B⊂CB\subset C or C⊂BC\subset B, for otherwise the union of BB and CC would be different from both BB and CC, so we would have three sets BB, CC and B∪CB\cup C of size at least nn. We see that in any case there must exist x∉Ax\notin A such that x∈Sjx\in S_j for all j∉Ij\notin I. Consider sets Sj′=Sj∖{x}S'_j = S_j\setminus\{x\} for j∉Ij\notin I. Their sizes are equal to k−1k-1. Their number is at least

N−(n−1k)=(n−1k−1)+1.N - \binom{n-1}{k} = \binom{n-1}{k-1} + 1.
By the induction hypothesis, we can form 33 sets of size at least n−1n-1 by taking unions of the sets Sj′S'_j for j∉Ij\notin I. Adding xx back we see that the corresponding unions of the sets SjS_j will have sizes at least nn, so we are done proving the induction step.

The above argument allows us to decrease kk all the way to k=0k = 0, so it remains to check the statement for k=0k = 0. The assumption says that we have at least (n0)+1=2\binom{n}{0} + 1 = 2 sets of size 00. This is impossible, because there is only one empty set. Thus the statement trivially holds for k=0k = 0.

Transcribed from the official solutions, page 3. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?