Soroljuk $X$ részhalmazait párokba úgy, hogy minden részhalmaz a komplementumával legyen egy párban. Mivel a párok száma $2^{k-1}>n$, van olyan pár, amelynek egyik tagja sem szerepel az $A_i$ halmazok között. Legyen egy ilyen pár két tagja $B$ és $C$. Ha az $A_i$ halmazok mindegyikének van közös eleme $B$-vel, akkor a $B$ halmaz megfelelő. Feltehetjük tehát, hogy például $A_1$ a $B$-vel diszjunkt, s így részhalmaza $C$-nek.
Ebben az esetben a $C$ halmaz lesz megfelelő. Valóban, minden egyes $A_i$ halmaznak van közös eleme $A_1$-gyel, ezért az $A_1$-et tartalmazó $C$-vel is.