, 2007

Let $k$ and $m$ be positive integers (to be determined later) and set $n = k m$. Decompose the set $\{1, 2, \ldots, n\}$ into $k$ disjoint subsets, each of size $m$; denote these subsets by $A_{1}, \ldots, A_{k}$. Define the following families of sets:
$$\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 \in \mathcal{T} \subset \mathcal{T}_{1}$, there exists an index $1 \leq i \leq k$ such that $A_{i} \subset T$. Then for all $S \in \mathcal{S}$, $S \cap T \supset S \cap A_{i} \neq \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}, \ldots, S_{p}$ and $T_{1}, \ldots, 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{equation*} |\mathcal{S}| = \left(2^{m} - 1\right)^{k} \tag{1} \end{equation*}$$
Similarly, if a set $H \subset \{1, 2, \ldots, 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{equation*} |\mathcal{T}_{1}| = 2^{k m} - \left(2^{m} - 1\right)^{k} \tag{2} \end{equation*}$$
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{equation*} |\mathcal{S} \setminus \mathcal{T}_{1}| = \left(2^{m} - 2\right)^{k} \tag{3} \end{equation*}$$
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^{k m} - 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
$$\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 \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 $m$ is sufficiently large then $\frac{|\mathcal{S}|}{2^{m k}}$ and $\frac{|\mathcal{T}|}{2^{m k}}$ are greater than $\alpha$ (since $\alpha < \delta$). So $|\mathcal{S}|, |\mathcal{T}| > \alpha \cdot 2^{m k} = \alpha \cdot 2^{n}$.