Track / Stage 6 / 10 of 400 #1650 of 2604

Problem 1650

National Olympiad, first round

Combinatorics Difficulty 6.0 Prove it KöMaL problem A · Hungary · 2014

Let $\mathcal{F}$ be a finite family of finite sets and let $A$ be an arbitrary finite set. We say that $\mathcal{F}$ shatters the set $A$ if for every $X\subseteq A$ there is a set $F\in \mathcal{F}$ such that $A\cap F=X$ . Show that $\mathcal{F}$ shatters at least $|\mathcal{F}|$ sets.
(5 pont)

This one wants a proof. Work it on paper, then check yourself against the publisher's own solution, linked below. Be honest about it: the record is only any use to you if it is.

We don't reproduce this publisher's solutions. Their own solution is here — work the problem first.

Source: KöMaL, licensed Rights held by KöMaL and the MATFUND Foundation. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project. Solutions are the publisher's, linked not copied.