Bound on number of breakable sets Let $\mathcal{S}$ be a finite family of finite sets. A finite set $A$ is called breakable if for every $B\subseteq A$, there exists $S\in \mathcal{S}$ such that $A\cap S=B$. Show that at least $|\mathcal{S}|$ sets are breakable.
[Source: Hungarian competition problem]
 A: Denote by $Br({\mathcal S})$ the set of sets that are breakable by $\mathcal S$. Let us
show by induction on $n=|{\mathcal S}|$ that 
$|Br({\mathcal{S}})| \geq |\mathcal{S}|$.
First, note that $\emptyset$ is always breakable (by any nonempty $\mathcal{S}$),
so that the result is true for $n\leq 1$. Next, suppose that $n>1$ and
that the result is true for any $\mathcal{S}$ with $|\mathcal{S}|<n$. We are going to show that the result
is true for $\mathcal{S}$ also.
Taking $B=A$ in the definition of a breakable set, we see that if $A$
is breakable by $\mathcal{S}$ then $A\subseteq S$ for some $S\in{\mathcal{S}}$.
It follows that
$$
\text{If} \ A\in Br({\mathcal S}), \text{ then } A\subseteq 
\bigcup_{S\in{\mathcal{S}}} S \tag{1}
$$ 
Since $n>1$, there are at least two distinct sets $S_1$ and $S_2$ in $\mathcal{S}$.
There must exist some $z$ differentiating the two, i.e. $z\in S_1\setminus S_2$
or $z\in S_2\setminus S_1$. Then $\lbrace z \rbrace$ is breakable by
$\lbrace S_1,S_2\rbrace$. Now, let
$$
{\mathcal{A}}=\lbrace S\setminus \lbrace z\rbrace \ | \ S\in{\mathcal{S}}, \
z\in S \rbrace, \ 
{\mathcal{B}}=\lbrace S \ | \ S\in{\mathcal{S}}, \ 
z\not\in S \rbrace \tag{2}
$$
Then $\mathcal{A}$ and $\mathcal{B}$ are both non-empty, and  $|{\mathcal{A}}|+|{\mathcal{B}}|=|\mathcal{S}|$. Next, define
$$
\left\lbrace\begin{array}{lcl}
C_1 &=& Br({\mathcal{A}}) \setminus Br({\mathcal{B}}), \\
C_2 &=& Br({\mathcal{B}}) \setminus Br({\mathcal{A}}), \\
C_3 &=& Br({\mathcal{A}}) \cap Br({\mathcal{B}}), \\ 
C_4 &=& \lbrace S\cup\lbrace z \rbrace \ | \  S\in C_3 \rbrace
\end{array}\right.\tag{3}
$$
We have $|C_1|+|C_3| \geq |{\mathcal{A}}|$ and $|C_2|+|C_3| \geq |{\mathcal{A}}|$
by the induction hypothesis. Note that the sets in $C_1,C_2$ or $C_3$ never 
contain $z$ by (1). I claim that 
$$
\text{Any set in } C_4 \text{ is breakable by } {\mathcal{S}}.\tag{4}
$$
To check that, let $A\in C_4$, $A=S\cup\lbrace z \rbrace$ with $S\in C_3$. Let 
$B\subseteq A$. If $z\not\in B$, then since $S\in Br({\mathcal B})$ 
there is a $T'\in {\mathcal B}$ such that
$S\cap T'=B$. Then $T=T'$ satisfies $T\in {\mathcal S}$ and $A\cap T=B$, so we are done in this case. If $z\in B$, then since $S\in Br({\mathcal B})$ 
there is a $T'\in {\mathcal A}$  such that $S\cap T'=B\setminus \lbrace z \rbrace$. Then $T=T'\cup \lbrace z \rbrace$ 
satisfies $T\in {\mathcal S}$ and $A\cap T=B$, so we are done in this case also. This concludes
the proof of (4).
It follows that $\bigcup_{i=1}^{4} C_i \subseteq Br(\mathcal{S})$, and hence
$$
\left\lbrace\begin{array}{lcl}
| Br(\mathcal{S})| & \geq& |C_1|+|C_2|+|C_3|+|C_4| \\
 &=& (|C_1|+|C_3||)+(|C_2|+|C_3|) \\
&\geq& |{\mathcal{A}}|+|{\mathcal{B}}| \\
 &=& |{\mathcal{S}}| \\
\end{array}\right.\tag{5}
$$
This concludes the proof.
