Feladat: F.2898 Korcsoport: 18- Nehézségi fok: átlagos
Megoldó(k):  Csermely Zoltán ,  Csorba Péter ,  Csörnyei Marianna ,  Faragó Gergely ,  Futó Gábor ,  Győry Máté ,  Horvai Péter ,  Horváth Gábor ,  Imreh Csanád ,  Kálmán Tamás ,  Köszegi Botond ,  Lente Gábor ,  Marx Gábor ,  Molnár-Sáska Gábor ,  Németh Ákos ,  Párniczky Benedek ,  Stőhr Lóránt ,  Szeidl Ádám ,  Tichler Krisztián ,  Tóth Csaba D. ,  Ujváry-Menyhárt Zoltán 
Füzet: 1992/december, 437 - 438. oldal  PDF file
Témakör(ök): Részhalmazok, Kombinatorika, Feladat
Hivatkozás(ok):Feladatok: 1992/március: F.2898

Legyenek A1, A2, ..., An egy k-elemű X halmaz részhalmazai. Tegyük fel, hogy közülük bármely kettőnek van közös eleme, és n<2k-1. Bizonyítsuk be, hogy ekkor X-nek létezik olyan részhalmaza, amely nem azonos egyik Ai-vel sem, de bármelyikkel van közös eleme.

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.

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

 

Ujváry-Menyhárt Zoltán (Fazekas M. Főv. Gyak. Gimn., IV. o. t.)

 

Megjegyzés. A 2k-1 korlát éles. Tekintsünk egy k elemű X halmazt. Legyen a az X egyik eleme, és legyenek A1, A2, ..., A2k-1 X-nek mindazok a részhalmazai, amelyek a-t tartalmazzák. Ezek közül bármelyik kettőnek van közös eleme (pl. az a). Ha viszont B egy ezektől különböző részhalmaz, akkor B nem tartalmazza a-t, így nincs közös eleme pl. az {a} halmazzal, amely az Ai-k között szerepel.
Ugyanerre egy másik példa: legyen k páratlan, és legyenek A1, ..., A2k-1 azok a részhalmazok, amelyek elemszáma legalább k+12. Ha B nem ilyen részhalmaz, akkor X\B szerepel az Ai-k között.