IMC 1997 · Day 1 · P6

a) No. Consider $F = \{ A_1, B_1, \dots, A_n, B_n, \dots \}$, where $A_n = \{ 1, 3, 5, \dots, 2n-1, 2n \}$, $B_n = \{ 2, 4, 6, \dots, 2n, 2n+1 \}$.

b) Yes. We will prove inductively a stronger statement:

Suppose $F$, $G$ are two families of finite subsets of $\mathbb{N}$ such that:

1) For every $A \in F$ and $B \in G$ we have $A \cap B \ne \emptyset$;

2) All the elements of $F$ have the same size $r$, and elements of $G$ – size $s$. (we shall write $\#(F) = r$, $\#(G) = s$).

Then there is a finite set $Y$ such that $A \cup B \cup Y \ne \emptyset$ for every $A \in F$ and $B \in G$.

The problem b) follows if we take $F = G$.

Proof of the statement: The statement is obvious for $r = s = 1$. Fix the numbers $r$, $s$ and suppose the statement is proved for all pairs $F'$, $G'$ with $\#(F') < r$, $\#(G') < s$. Fix $A_0 \in F$, $B_0 \in G$. For any subset $C \subset A_0 \cup B_0$, denote $$F(C) = \{ A \in F : A \cap (A_0 \cup B_0) = C \}.$$ Then $F = \bigcup\limits_{\emptyset \ne C \subset A_0 \cup B_0} F(C)$. It is enough to prove that for any pair of non-empty sets $C, D \subset A_0 \cup B_0$ the families $F(C)$ and $G(D)$ satisfy the statement.

Indeed, if we denote by $Y_{C,D}$ the corresponding finite set, then the finite set $\bigcup\limits_{C, D \subset A_0 \cup B_0} Y_{C,D}$ will satisfy the statement for $F$ and $G$. The proof for $F(C)$ and $G(D)$.

If $C \cap D \ne \emptyset$, it is trivial.

If $C \cap D = \emptyset$, then any two sets $A \in F(C)$, $B \in G(D)$ must meet outside $A_0 \cup B_0$. Then if we denote $\widetilde{F}(C) = \{ A \setminus C : A \in F(C) \}$, $\widetilde{G}(D) = \{ B \setminus D : B \in G(D) \}$, then $\widetilde{F}(C)$ and $\widetilde{G}(D)$ satisfy the conditions 1) and 2) above, with $\#(\widetilde{F}(C)) = \#(F) - \#C < r$, $\#(\widetilde{G}(D)) = \#(G) - \#D < s$, and the inductive assumption works.