48th International Mathematical Olympiad Vietnam 2007 Shortlisted Problems with Solutions

Let $k$ and $m$ be positive integers (to be determined later) and set $n=km$. Decompose the set $\{1,2,\dots ,n\}$ into $k$ disjoint subsets, each of size $m$; denote these subsets by $A_1,\dots ,A_k$. Define the following families of sets: $$\begin{array}{rl}\mathcal{S}& =\left\{S\subset \{1,2,\dots ,n\}:\forall iS\cap A_i\ne \varnothing \right\},\\ {\mathcal{T}}_1& =\left\{T\subset \{1,2,\dots ,n\}:\exists i{A}_i\subset T\right\},\mathcal{T}={\mathcal{T}}_1\setminus \mathcal{S}.\end{array}$$ For each set $T\in \mathcal{T}\subset {\mathcal{T}}_1$, there exists an index $1\le i\le k$ such that $A_i\subset T$. Then for all $S\in \mathcal{S}$, $S\cap T\supset S\cap A_i\ne \varnothing$. Hence, each $S\in \mathcal{S}$ and each $T\in \mathcal{T}$ have at least one common element.

Below we show that the numbers $m$ and $k$ can be chosen such that $|\mathcal{S}|,|\mathcal{T}|>\alpha \cdot 2^n$. Then, choosing $p=\min \{|\mathcal{S}|,|\mathcal{T}|\}$, one can select the desired $2p$ sets $S_1,\dots ,S_p$ and $T_1,\dots ,T_p$ from families $\mathcal{S}$ and $\mathcal{T}$, respectively. Since families $\mathcal{S}$ and $\mathcal{T}$ are disjoint, sets $S_i$ and $T_j$ will be pairwise distinct.

To count the sets $S\in \mathcal{S}$, observe that each $A_i$ has $2^m-1$ nonempty subsets so we have $2^m-1$ choices for $S\cap A_i$. These intersections uniquely determine set $S$, so $$\begin{array}{c}|\mathcal{S}|={\left(2^m-1\right)}^k\end{array}\text{\hspace{1em}(1)}$$ Similarly, if a set $H\subset \{1,2,\dots ,n\}$ does not contain a certain set $A_i$ then we have $2^m-1$ choices for $H\cap A_i$: all subsets of $A_i$, except $A_i$ itself. Therefore, the complement of ${\mathcal{T}}_1$ contains ${\left(2^m-1\right)}^k$ sets and $$\begin{array}{c}|{\mathcal{T}}_1|=2^{km}-{\left(2^m-1\right)}^k\end{array}\text{\hspace{1em}(2)}$$ Next consider the family $\mathcal{S}\setminus {\mathcal{T}}_1$. If a set $S$ intersects all $A_i$ but does not contain any of them, then there exists $2^m-2$ possible values for each $S\cap A_i$: all subsets of $A_i$ except $\varnothing$ and $A_i$. Therefore the number of such sets $S$ is ${\left(2^m-2\right)}^k$, so $$\begin{array}{c}|\mathcal{S}\setminus {\mathcal{T}}_1|={\left(2^m-2\right)}^k\end{array}\text{\hspace{1em}(3)}$$ From (1), (2), and (3) we obtain $$|\mathcal{T}|=|{\mathcal{T}}_1|-|\mathcal{S}\cap {\mathcal{T}}_1|=|{\mathcal{T}}_1|-(|\mathcal{S}|-|\mathcal{S}\setminus {\mathcal{T}}_1|)=2^{km}-2{\left(2^m-1\right)}^k+{\left(2^m-2\right)}^k$$ Let $\delta =\frac{3-\sqrt{5}}{2}$ and $k=k(m)=\left[2^m\log \frac{1}{\delta }\right]$. Then $$\underset{m\to \infty }{\lim }\frac{|\mathcal{S}|}{2^{km}}=\underset{m\to \infty }{\lim }{\left(1-\frac{1}{2^m}\right)}^k=\exp \left(-\underset{m\to \infty }{\lim }\frac{k}{2^m}\right)=\delta$$ and similarly $$\underset{m\to \infty }{\lim }\frac{|\mathcal{T}|}{2^{km}}=1-2\underset{m\to \infty }{\lim }{\left(1-\frac{1}{2^m}\right)}^k+\underset{m\to \infty }{\lim }{\left(1-\frac{2}{2^m}\right)}^k=1-2\delta +{\delta }^2=\delta$$ Hence, if $m$ is sufficiently large then $\frac{|\mathcal{S}|}{2^{mk}}$ and $\frac{|\mathcal{T}|}{2^{mk}}$ are greater than $\alpha$ (since $\alpha <\delta$). So $|\mathcal{S}|,|\mathcal{T}|>\alpha \cdot 2^{mk}=\alpha \cdot 2^n$.