Maths Olympiad Prep

Library / /683 of 1394

, 2020

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:
Let n>1n > 1 be a positive integer and SS be a collection of 12(2nn)\frac{1}{2}\binom{2n}{n} distinct nn-element subsets of {1,2,,2n}\{1,2, \ldots, 2n\}. Show that there exists A,BSA, B \in S such that AB1|A \cap B| \leq 1.

Solutions — 2

Solution 1

Solution:
Assume for the sake of contradiction that there exist no such A,BA, B. Pair up each subset with its complement, like so:
{1,2,3,,n}{n+1,n+2,,2n}{1,2,3,,n1,n+1}{n,n+2,,2n}{1,2,3,,n1,n+2}{n,n+1,n+3,,2n} \begin{aligned} \{1,2,3, \ldots, n\} & \leftrightarrow \{n+1, n+2, \ldots, 2n\} \\ \{1,2,3, \ldots, n-1, n+1\} & \leftrightarrow \{n, n+2, \ldots, 2n\} \\ \{1,2,3, \ldots, n-1, n+2\} & \leftrightarrow \{n, n+1, n+3, \ldots, 2n\} \\ & \vdots \end{aligned}
Note that for each pair, we can have at most one of the two in SS. Since SS has 12\frac{1}{2} of the total number of subsets with size nn, it must be that we have exactly one element from each pair in SS. For any s0Ss_{0} \in S, none of the subsets that share exactly one element with s0s_{0} can be in SS, so their complements must be in SS. This means that every subset with n1n-1 shared elements with s0s_{0} must be in SS. Without loss of generality, assume {1,2,3,,n}S\{1,2,3, \ldots, n\} \in S. Then, {2,3,4,,n+1}S\{2,3,4, \ldots, n+1\} \in S, so {3,4,5,,n+2}S\{3,4,5, \ldots, n+2\} \in S. Continuing on in this manner, we eventually reach {n+1,n+2,,2n}S\{n+1, n+2, \ldots, 2n\} \in S, contradiction.

Solution 2

Solution:
Let [2n]={1,2,,2n}[2n] = \{1,2, \ldots, 2n\}. Consider the following cycle of 2n12n-1 sets such that any two adjacent sets have an intersection of size 11:
{1,2,3,,n}{1,n+1,n+2,,2n1}{1,2n,2,3,,n1}{1,n+2,n+3,,2n} \begin{aligned} & \{1,2,3, \ldots, n\} \\ & \{1, n+1, n+2, \ldots, 2n-1\} \\ & \{1, 2n, 2,3, \ldots, n-1\} \\ & \vdots \\ & \{1, n+2, n+3, \ldots, 2n\} \end{aligned}
If SS contains two adjacent elements of the cycle then we are done. For each permutation σ\sigma of [2n][2n], we can consider the cycle CσC_{\sigma} of sets obtained after applying σ\sigma, i.e. {σ(1),σ(2),σ(3),,σ(n)}\{\sigma(1), \sigma(2), \sigma(3), \ldots, \sigma(n)\} and so on. In total, each subset of [2n][2n] with size nn appears (2n1)(n!)2(2n-1)(n!)^{2} times across all the cycles CσC_{\sigma}, so
σCσS=S(2n1)(n!)2=2n12(2n)! \sum_{\sigma} |C_{\sigma} \cap S| = |S| (2n-1)(n!)^{2} = \frac{2n-1}{2} (2n)!
where the sum is over all (2n)!(2n)! permutations of [2n][2n]. This means that on average across possible cycles, 2n12\frac{2n-1}{2} of its elements are in SS. Thus, if we select a cycle CσC_{\sigma} uniformly at random, with positive probability we will have CσSn|C_{\sigma} \cap S| \geq n, so two adjacent elements in this cycle will be in SS. Therefore, there must exist some two subsets in SS that share at most one element.

This proof will work under the weaker condition S>n12n1(2nn)|S| > \frac{n-1}{2n-1} \binom{2n}{n}.

Remark. A family of sets such that ABt|A \cap B| \geq t for every pair of distinct sets A,BA, B is called tt-intersecting. Ahlswede and Khachatrian solved the problem of determining the largest kk-uniform tt-intersecting family. See "Katona's Intersection Theorem: Four Proofs" or "The Complete Intersection Theorem for Systems of Finite Sets" for exact results.

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.