Consider a set $X$ with $|X| = n\geq 1$ elements. A family $\mathcal{F}$ of distinct subsets of $X$ is said to have property $\mathcal{P}$ if there exist $A,B \in \mathcal{F}$ so that $A\subset B$ and $|B\setminus A| = 1$. i) Determine the least value $m$, so that any family $\mathcal{F}$ with $|\mathcal{F}| > m$ has property $\mathcal{P}$. ii) Describe all families $\mathcal{F}$ with $|\mathcal{F}| = m$, and not having property $\mathcal{P}$. (Dan Schwarz)
Problem
Source: Stars of Mathematics 2012, Juniors, Problem 4
Tags: combinatorics, boolean lattice method
28.03.2017 01:17
We claim that $\boxed{m=2^{n-1}}$. Take any $x\in X$, and consider pairs $\{S,S\cup\{x\}\}$, where $S\in\mathcal P(X-x)$. The crux of the solution is that $$\mathcal P(X)=\bigcup_{S\in\mathcal P(X-x)}\{S,S\cup\{x\}\}.\qquad(\bigstar)$$By the pigeonhole principle, if $|\mathcal F|>2^{n-1}$, then we can find a pair $\{S_0,S_0\cup\{x\}\}\in\mathcal F$, which satisfies the conditions. Note that the following two families have $2^{n-1}$ elements but not the property $\mathcal P$, proving that the bound is tight: $$\begin{cases}\mathcal F=\{S\in\mathcal P(X):|S|\equiv0\pmod{2}\},\\\mathcal F=\{S\in\mathcal P(X):|S|\equiv1\pmod{2}\}.\end{cases}$$We claim that these are the only such families, solving (ii). The result is a consequence of the following two lemmas. Lemma 1. Given $0\leq k<n$, if $\{S\in\mathcal P(x):|S|=k\}\subset\mathcal F$, then $\{S\in\mathcal P(x):|S|=k+1\}\cap\mathcal F=\emptyset$. Proof. For any $B\in\mathcal P(X)$ with $|B|=k+1$, take $x\in B$ and $A=B-x$. Then $A\in\mathcal F$, and so $B\not\in\mathcal F$, since otherwise $\mathcal F$ would have property $\mathcal P$. $\square$ Lemma 2. If $\{S\in\mathcal P(x):|S|=k\}\cap\mathcal F=\emptyset$, then $\{S\in\mathcal P(x):|S|=k+1\}\subset\mathcal F$. Proof. For any $B\in\mathcal P(X)$ with $|B|=k+1$, take $x\in B$ and $A=B-x$. Then $A\not\in\mathcal F$, and since $\mathcal F$ must contain exactly one element of each pair in the partition $(\bigstar)$, we must have $B\in\mathcal F$. $\square$
28.03.2017 01:40
This problem is trivialized by the following idea: Consider the "natural" way to draw the hypercube graph, $B_n$ (note: B comes from the term "Boolean Lattice"). This graph is a natural representation of the family of subsets of $[n]$, and furthermore, each edge is directly bijective with the pairs of sets that together give property $\mathcal{P}$. The first result follows immediately by choosing some (any!) axis and "collapsing" $B_n$ in accordance to it. Now color the vertices of $B_n$ into two demicubes. Also consider that the "complement" of a family of size $2^{n-1}$ who has property $\mathcal{P}$ must, again by pigeonholes, have property $\mathcal{P}$. The result follows by choosing some vertex (there is surely at least one!) in our family and "walking" outwards until we have covered the hypercube.