Maths Olympiad Prep

Library / IMO Shortlist /220 of 365

IMO Shortlist, 2007

Combinatorics Difficulty 8.7 Shortlist Prove it IMO

Let α<3−52\alpha < \frac{3 - \sqrt{5}}{2} be a positive real number. Prove that there exist positive integers nn and p>α⋅2np > \alpha \cdot 2^{n} for which one can select 2p2p pairwise distinct subsets S1,…,Sp,T1,…,TpS_{1}, \ldots, S_{p}, T_{1}, \ldots, T_{p} of the set {1,2,…,n}\{1, 2, \ldots, n\} such that Si∩Tj≠∅S_{i} \cap T_{j} \neq \varnothing for all 1≤i,j≤p1 \leq i, j \leq p.

Solution

Let kk and mm be positive integers (to be determined later) and set n=kmn = k m. Decompose the set {1,2,…,n}\{1, 2, \ldots, n\} into kk disjoint subsets, each of size mm; denote these subsets by A1,…,AkA_{1}, \ldots, A_{k}. Define the following families of sets:
S={S⊂{1,2,…,n}:∀i S∩Ai≠∅},T1={T⊂{1,2,…,n}:∃i Ai⊂T},T=T1∖S. \begin{aligned} \mathcal{S} & = \left\{ S \subset \{1, 2, \ldots, n\} : \forall i\ S \cap A_{i} \neq \varnothing \right\}, \\ \mathcal{T}_{1} & = \left\{ T \subset \{1, 2, \ldots, n\} : \exists i\ A_{i} \subset T \right\}, \quad \mathcal{T} = \mathcal{T}_{1} \setminus \mathcal{S} . \end{aligned}
For each set T∈T⊂T1T \in \mathcal{T} \subset \mathcal{T}_{1}, there exists an index 1≤i≤k1 \leq i \leq k such that Ai⊂TA_{i} \subset T. Then for all S∈SS \in \mathcal{S}, S∩T⊃S∩Ai≠∅S \cap T \supset S \cap A_{i} \neq \varnothing. Hence, each S∈SS \in \mathcal{S} and each T∈TT \in \mathcal{T} have at least one common element.

Below we show that the numbers mm and kk can be chosen such that ∣S∣,∣T∣>α⋅2n|\mathcal{S}|, |\mathcal{T}| > \alpha \cdot 2^{n}. Then, choosing p=min⁡{∣S∣,∣T∣}p = \min \{|\mathcal{S}|, |\mathcal{T}|\}, one can select the desired 2p2p sets S1,…,SpS_{1}, \ldots, S_{p} and T1,…,TpT_{1}, \ldots, T_{p} from families S\mathcal{S} and T\mathcal{T}, respectively. Since families S\mathcal{S} and T\mathcal{T} are disjoint, sets SiS_{i} and TjT_{j} will be pairwise distinct.

To count the sets S∈SS \in \mathcal{S}, observe that each AiA_{i} has 2m−12^{m} - 1 nonempty subsets so we have 2m−12^{m} - 1 choices for S∩AiS \cap A_{i}. These intersections uniquely determine set SS, so
∣S∣=(2m−1)k \begin{equation*} |\mathcal{S}| = \left(2^{m} - 1\right)^{k} \tag{1} \end{equation*}
Similarly, if a set H⊂{1,2,…,n}H \subset \{1, 2, \ldots, n\} does not contain a certain set AiA_{i} then we have 2m−12^{m} - 1 choices for H∩AiH \cap A_{i}: all subsets of AiA_{i}, except AiA_{i} itself. Therefore, the complement of T1\mathcal{T}_{1} contains (2m−1)k\left(2^{m} - 1\right)^{k} sets and
∣T1∣=2km−(2m−1)k \begin{equation*} |\mathcal{T}_{1}| = 2^{k m} - \left(2^{m} - 1\right)^{k} \tag{2} \end{equation*}
Next consider the family S∖T1\mathcal{S} \setminus \mathcal{T}_{1}. If a set SS intersects all AiA_{i} but does not contain any of them, then there exists 2m−22^{m} - 2 possible values for each S∩AiS \cap A_{i}: all subsets of AiA_{i} except ∅\varnothing and AiA_{i}. Therefore the number of such sets SS is (2m−2)k\left(2^{m} - 2\right)^{k}, so
∣S∖T1∣=(2m−2)k \begin{equation*} |\mathcal{S} \setminus \mathcal{T}_{1}| = \left(2^{m} - 2\right)^{k} \tag{3} \end{equation*}
From (1), (2), and (3) we obtain
∣T∣=∣T1∣−∣S∩T1∣=∣T1∣−(∣S∣−∣S∖T1∣)=2km−2(2m−1)k+(2m−2)k |\mathcal{T}| = |\mathcal{T}_{1}| - |\mathcal{S} \cap \mathcal{T}_{1}| = |\mathcal{T}_{1}| - (|\mathcal{S}| - |\mathcal{S} \setminus \mathcal{T}_{1}|) = 2^{k m} - 2\left(2^{m} - 1\right)^{k} + \left(2^{m} - 2\right)^{k}
Let δ=3−52\delta = \frac{3 - \sqrt{5}}{2} and k=k(m)=[2mlog⁡1δ]k = k(m) = \left[2^{m} \log \frac{1}{\delta}\right]. Then
lim⁡m→∞∣S∣2km=lim⁡m→∞(1−12m)k=exp⁡(−lim⁡m→∞k2m)=δ \lim_{m \rightarrow \infty} \frac{|\mathcal{S}|}{2^{k m}} = \lim_{m \rightarrow \infty} \left(1 - \frac{1}{2^{m}}\right)^{k} = \exp\left(-\lim_{m \rightarrow \infty} \frac{k}{2^{m}}\right) = \delta
and similarly
lim⁡m→∞∣T∣2km=1−2lim⁡m→∞(1−12m)k+lim⁡m→∞(1−22m)k=1−2δ+δ2=δ \lim_{m \rightarrow \infty} \frac{|\mathcal{T}|}{2^{k m}} = 1 - 2 \lim_{m \rightarrow \infty} \left(1 - \frac{1}{2^{m}}\right)^{k} + \lim_{m \rightarrow \infty} \left(1 - \frac{2}{2^{m}}\right)^{k} = 1 - 2\delta + \delta^{2} = \delta
Hence, if mm is sufficiently large then ∣S∣2mk\frac{|\mathcal{S}|}{2^{m k}} and ∣T∣2mk\frac{|\mathcal{T}|}{2^{m k}} are greater than α\alpha (since α<δ\alpha < \delta). So ∣S∣,∣T∣>α⋅2mk=α⋅2n|\mathcal{S}|, |\mathcal{T}| > \alpha \cdot 2^{m k} = \alpha \cdot 2^{n}.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.