A finite family of finite sets $F$ is given, satisfying two conditions: (i) if $A, B \in F$, then $A \cup B \in F$; (ii) if $A \in F$, then the number of elements $| A |$ is not a multiple of $3$. Prove that you can specify at most two elements so that every set of the family $F$ contains at least one of them.
Problem
Source: 2016 239 S6
Tags: combinatorics
27.11.2021 19:56
Very very nice problem! Before we begin, observe that for any fixed $\mathcal{F}$, we may increase $|F|=n$ to any value we want without affecting the problem. Hence, in what follows, we assume $n\equiv 2 \pmod{3}$. For any set $X\in \mathcal{F}$, denote by $X'$ the set of all unordered pairs $(x,y)$ with $x,y\in S$ s.t. at least one of $x,y\in X$. We present 3 claims. Claim 1: For any $A\in \mathcal{F}$, $|A'|\equiv 1 \pmod{3}$. Proof: A direct computation gives \begin{align*} |A'|=\binom{|A|}{2}+(|A|)(n-|A|)=\frac{|A|}{2}(|A|-1+2n-2|A|)&=\frac{|A|[(2n-1)-|A|]}{2} \\ &\equiv \frac{-|A|^2}{2}\equiv \frac{-1}{2} \equiv 1 \pmod{3} \end{align*}since $3\nmid |A|$. $\square$ Claim 2: For any $A_1,A_2,...,A_m\in \mathcal{F}$, $|(A_1\cup A_2\cup ...\cup A_m)'|=|A_1'\cup A_2' \cup ...\cup A_m'|$. Proof: We first prove $(A_1\cup A_2)'=A_1'\cup A_2'$. Observe that \begin{align*} &(x,y)\in (A_1\cup A_2)' \quad\Leftrightarrow\quad x\text{ or }y\in A_1\cup A_2 \quad\Leftrightarrow\quad x\text{ or }y\in A_1\text{ or }A_2 \\ &\Leftrightarrow\quad (x,y)\in A_1'\text{ or }A_2' \quad\Leftrightarrow\quad (x,y)\in A_1'\cup A_2', \end{align*}so $(A_1\cup A_2)'=A_1'\cup A_2'$. The statement of the claim then follows by applying the above repeatedly: \[|(A_1\cup A_2\cup ...\cup A_m)'|=|A_1'\cup (A_2\cup ...\cup A_m)'|=|A_1'\cup A_2'\cup (A_3\cup ...\cup A_m)'|=...=|A_1'\cup A_2' \cup ...\cup A_m'|\quad\square\] Claim 3: For any $A_1,A_2,...,A_m\in \mathcal{F}$, $|A_1'\cap A_2'\cap ...\cap A_m'|\equiv 1\pmod{3}$. Proof: We perform induction on $m$. The base case $m=1$ is proved in Claim 1. Now assume the statement is true for $m=k$; we shall prove it for $m=k+1$. By Claim 2 together with the inclusion-exclusion principle, we have \begin{align*} |(A_1\cup ...\cup A_{k+1})'|&=|A_1'|+...-|A_1'\cap A_2'|-...+|A_1'\cap A_2'\cap A_3'|+...+(-1)^k|A_1'\cap...\cap A_{k+1}'| \\ 1&\equiv\binom{k+1}{1}(1)-\binom{k+1}{2}(1)+...+(-1)^k\binom{k+1}{k+1}|A_1'\cap...\cap A_{k+1}'| \pmod{3} \\ 0&\equiv-(1-1)^{k+1}-(-1)^k\binom{k+1}{k+1}(1)+(-1)^k\binom{k+1}{k+1}|A_1'\cap...\cap A_{k+1}'| \pmod{3} \\ |A_1'\cap...\cap A_{k+1}'|&\equiv 1 \pmod{3} \end{align*}This completes the inductive step. $\square$ We are ready to finish. Applying Claim 3 to all sets in $\mathcal{F}$, we see that there exists a pair $(x,y)$ with $x,y\in S$ s.t. every set in $\mathcal{F}$ contains at least one of $x,y$. This is the $x,y$ we seek. $\blacksquare$ Remark. I personally found inspiration from trying to prove the problem with $3$ replaced by $2$ (and $x,y$ replaced by $x$ only). It didn't require the construction of $X'$, but gave me the idea of using the inclusion-exclusion principle and induction on intersection of sets.