Feladat: F.2479 Korcsoport: 16-17 Nehézségi fok: nehéz
Füzet: 1985/március, 110 - 111. oldal  PDF file
Témakör(ök): Részhalmazok, Halmazok számossága, Konstruktív megoldási módszer, Teljes indukció módszere, Feladat
Hivatkozás(ok):Feladatok: 1984/május: F.2479

Legfeljebb hány nem-üres részhalmaz választható ki egy 100 elemű halmazból úgy, hogy bármely két kiválasztott részhalmaz vagy diszjunkt legyen vagy az egyik tartalmazza a másikat ?

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Legyen a 100 elemű halmaz az 1, 2, ..., 100 számok halmaza. Válasszuk ki összes egyelemű részhalmazát, valamint az {1,2,...,n} alakú halmazokat, ahol n=2, 3, ..., 100. Az így kiválasztott 199 részhalmaz teljesíti a feladat feltételeit. Megmutatjuk, hogy 200 részhalmazt már nem lehet úgy kiválasztani, hogy teljesítse a feladat feltételeit, tehát a feladat kérdésére a válasz 199.
Általában azt mutatjuk meg, hogy egy n elemű halmazból legfeljebb 2n-1 részhalmaz választható ki a feladat feltételeinek megfelelően. A bizonyítást teljes indukcióval végezzük, n=1-re ez nyilván igaz. Tegyük most fel, hogy az állítás minden n-nél kisebb természetes számra igaz, és válasszuk ki egy n elemű H halmazból a lehető legtöbb részhalmazt úgy, hogy a részhalmazok eleget tegyenek a feltételeknek. Nyilvánvaló, hogy H szerepelni fog a kiválasztottak között, hiszen ha nem szerepelne, hozzá vehetnénk, hiszen minden kiválasztott részhalmaz része H-nak. Bebizonyítjuk, hogy valódi részhalmazok közül legföljebb 2n-2 szerepelhet. Legyen A az (egyik) legnagyobb elemszámú a kiválasztott valódi részhalmazok között, és jelöljük A elemszámát a-val. A feltételnek megfelelően minden további részhalmaz vagy része A-nak, vagy tartalmazza A-t, vagy diszjunkt tőle. De A-t tartalmazó valódi részhalmaz nem lehet, mert A elemszáma maximális volt. Tehát a további kiválasztott részhalmazok között kétféle van: olyan, amelyik része A-nak, s olyan, amelyik diszjunkt tőle.
Azok, amelyek részhalmazai A-nak, A-val együtt egy olyan részrendszerét alkotják A-nak, amely teljesíti a feladat feltételét. A elemszáma kisebb n-nél, ezért az indukciós feltétel szerint egy ilyen részhalmaz-rendszerben legföljebb 2a-1 halmaz lehet. Az A-tól diszjunkt részhalmazok szintén teljesítik a feladat feltételét, és mind részhalmazai A komplementerének, H-A-nak, amely n-a1 elemű, mivel A nem üres. Így (H-A )-ból az indukciós feltevés szerint legfeljebb 2(n-a)-1 részhalmazt lehet kiválasztani a feladat kívánalmainak megfelelően. Azt kaptuk, hogy legfeljebb 2a-1 olyan részhalmaz lehet, amely A-nak része, és legföljebb 2(n-a)-1, amely A-tól diszjunkt. H-val együtt tehát legfeljebb 1+(2a-1)+2(n-a)-1=2n-1 valódi részhalmazt választhattunk ki, ahogy állítottuk.
Ezzel beláttuk, hogy egy n elemű halmazból legfeljebb 2n-1 nem üres részhalmaz választható ki a feladat kívánalmainak megfelelően.

 

Megjegyzések. 1. A megoldás elején adott példa nyilvánvalóan általánosítható: n elemű halmazból mindig ki is választható 2n-1 részhalmaz a feladat előírásai szerint.
2. A bizonyítást végiggondolva megadhatjuk általánosan az összes olyan 2n-1 elemű részhalmaz-rendszert, amely eleget tesz a feladat követelményeinek: kiválasztjuk a teljes halmazt, majd minden lépésben tetszőlegesen két részre vágunk egy már kiválasztott, de még "fel nem vágott'' halmazt, és az így keletkezett két részhalmazát is kiválasztjuk. Az eljárást addig folytatjuk, amíg minden "fel nem vágott'' halmaz egy elemű nem lesz. Így, mint könnyen belátható, 2n-1 részhalmazt kapunk, ami jó, és másképp nem kaphatunk 2n-1 jó részhalmazt.
3. A bizonyítás során kétszer "segítettünk magunkon'' általános ötlettel. Először teljes indukciót használtunk, másodszor az A halmazt ügyesen választottuk: azt mondtuk, legyen a lehető legnagyobb. Ezzel a magunk számára áttekinthetőbbé tettük a halmazrendszert. Mindkét ötlet gyakran használható kombinatorikai feladatok megoldásában.