Ha van benne 1 elemű halmaz is, akkor az az elem mindegyik részhalmazban benne kell legyen. Ez szerencsésen biztosítja azt is, hogy bármelyik kettő metszetében is benne van ez az elem, tehát a metszet nem üres halmaz. Vagyis kiválasztjuk bármelyik elemet közös elemnek, a maradék n-1 elemnek pedig 2n-1 féle részhalmaza lehet. Abban benne van az üres halmaz is, az adja a kiválasztott elemmel együtt az 1 elemű halmazt.

Lássuk be, hogy 2n-1-nél több nem lehet. Az összes részhalmazok száma, amiből válogatni lehet, az 2ⁿ (ebben az üres halmaz is benne van de nem baj). Ha kiválasztjuk a H részhalmazt, akkor H komplementere nem lehet a kiválasztottak között, mert annak H-val nincs közös eleme. Vagyis mindegyik kiválasztotthoz tartozik egy, amit tuti nem választhatunk ki. Ezért biztos, hogy 2ⁿ/2-nél több nem lehet a részhalmazok száma.

Mivel az első részben találtunk is olyat, mi pontosan 2ⁿ/2 elemű, az a megoldás.

Rantnad megjegyzése teljesen jogos, külön meg kell nézni azt, hogy mi van, ha n=0. Az üres halmaznak csak az üres halmaz a részhalmaza, tehát nincs két részhalmaz, amik között metszetet lehet nézni. Hmm, értelmezés kérdése, hogy ilyenkor a feladat milyen feltételt vár el. Én arra hajlok, hogy ekkor a válasz 0 (mert a bármelyik kettő ilyenkor azt jelentheti, hogy az egy szem üres részhalmaz önmagával vett metszetéről van szó), de meg lehetne győzni arról is, hogy 1.
Rantnad, szerinted melyik a jobb?