uniolympiads English

IMC 2016, Ημέρα 1, Θέμα 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.

Πρωτότυπο από το επίσημο 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.

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(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.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 3. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;