Let $\mathcal{F}$ be a family of (distinct) subsets of the set $\{1,2,\dots,n\}$ such that for all $A$, $B\in \mathcal{F}$,we have that $A^C\cup B\in \mathcal{F}$, where $A^C$ is the set of all members of ${1,2,\dots,n}$ that are not in $A$. Prove that every $k\in {1,2,\dots,n}$ appears in at least half of the sets in $\mathcal{F}$. Stijn Cambie, Mohammad Javad Moghaddas Mehr
Problem
Source: European Mathematical Cup, 2024/J4
Tags: combinatorics, Subsets, emc
24.12.2024 03:06
Consider any arbitrary element $k$. Let $X$ be the set of sets in $\mathcal{F}$ containing $k$, and let $Y$ be the set of sets in $\mathcal{F}$ not containing $k$. Now, for any family of sets $A$ and $B$, define \[f(A,B)=\{a\cup b \mid a\in A, b\in B\},\]and let \[Y^*=\{y^C\mid y\in Y\}.\] Note that $f(Y^*,Y)\subseteq \mathcal{X}$, since all elements of $f(Y^*,Y)$ must both contain $k$ and be in $\mathcal{F}$ (by the problem condition). This means that \[|f(Y^*,Y)|\le |X|,\]and to prove that at least half of the sets have $k$ in them, it suffices to show that \[|Y|\le |f(Y^*,Y)| \implies |Y|\le |X|.\] To do this, let $X_1$, $X_2$, $\dots$, $X_i$ be the sets in $X$ and let $Y_1$, $Y_2$, $\dots$, $Y_i$ be the sets in $Y$. Now let $y$ be any set in $Y$. Note that by compounding the problem condition, we get that \[S=X_1^C\cup X_2^C\cup \dots \cup X_i^C \cup y\in \mathcal{F},\]which also lies in $Y$ because $k$ is not in $S$. Additionally, note that \[Y_1\cup Y_2\cup \dots \cup Y_j \subseteq S,\]which means that $S^C$ is disjoint from all of the sets in $Y$. Therefore, if we take \[Q=\{S^C\cup y \mid y\in Y\},\]we get that $|Q|=|Y|$ (since all sets must be different). Additionally, since $S\in Y$, we get that \[Q\subseteq f(Y^*,Y) \implies |Q|\le |f(Y^*,Y)|,\]or $|Y|\le |f(Y^*,Y)|$, as desired. This means that $|Y|\le |X|$, meaning that $k$ is in at least half of the subsets, finishing our proof.
25.12.2024 10:52
Note that $(A^C \cup B)$ is the set of elements that are in $B$ and in $A$, in $B$ and not in $A$, and those that are in neither $A$ or $B$, so its complement is those elements that are in $A$ but not $B$, so $(A^C \cup B)^C \cup B = A \cup B \in \mathcal F$. Then consider the subfamily $X$ of sets not containing $k$. There must exist some set in $X$ with the largest number of elements, otherwise if we had a tie we could take their union which would have more elements. This largest element must contain every other set in $X$, otherwise if we had some set that did not fit inside we could take their union which would have more elements and contradict the largest set property. Let this largest set be $K$. Then taking $K^{C} \cup S$ for all $S$ in $X$ provides a new family of sets that are guaranteed to be in $\mathcal F$, are all distinct (note that $K^C$ has zero intersection with all of the elements of $X$), and all contain $k$ since $k \in K^C$, so there are at least as many sets in $\mathcal F$ containing $k$ as how many do not contain $k$, done.