Feladat: Gy.3044 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Csóka Antal ,  Frenkel Péter ,  Gyenes Zoltán ,  Hangya Balázs ,  Juhász András ,  Kutalik Zoltán ,  Reviczky Ágnes ,  Szabó Jácint 
Füzet: 1996/november, 481 - 482. oldal  PDF  |  MathML 
Témakör(ök): Részhalmazok, Halmazok számossága, Gyakorlat
Hivatkozás(ok):Feladatok: 1996/február: Gy.3044

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.

Először megmutatjuk, hogy bármely kijelölt R részhalmaznak pontosan m eleme van. Mivel R valódi részhalmaz, azért létezik egy benne nem lévő p elem. Minden qR elemnek megfeleltetve az (a) szerint egyértelműen létező, p-t és q-t tartalmazó S kijelölt részhalmazt, kölcsönösen egyértelmű megfeleltetést kapunk R elemei és a p-t tartalmazó, R-t metsző kijelölt részhalmazok közt. Tehát minden kijelölt részhalmaz m elemet tartalmaz.
A (b) feltételből következik, hogy minden p elemet pontosan m+n kijelölt részhalmaz tartalmaz. Rögzítsük most H-nak egy r elemét. Az r-től különböző elemek mindegyike ‐ (a) miatt ‐ pontosan egy r-t tartalmazó részhalmazhoz tartozik hozzá. Az r-t m+n részhalmaz tartalmazza, és ezek mindegyikében m-1 darab r-től különböző elem van; ezért H-nak összesen h=1+(m+n)(m-1) eleme van.
A kijelölt részhalmazok száma legyen k. Számoljuk össze azon (p,R) párokat, ahol p a H-nak egy eleme, R egy kijelölt részhalmaz, és pR. Mivel h elemünk van, és mindegyik m+n részhalmazban van benne, azért az ilyen párok száma h(m+n). A számolást viszont úgy is elvégezhetjük, hogy a k darab kijelölt részhalmaz mindegyike m elemet tartalmaz, ezért a párok száma km. A kétféle számolás eredményének meg kell egyeznie, ezért km=h(m+n), ahonnan kapjuk, hogy

k=h(m+n)m=[1+(m+n)(m-1)](m+n)m.

 Frenkel Péter (Fazekas M. Főv. Gyak. Gimn., III. o.t.) dolgozata alapján

 
Megjegyzés. A feladathoz nem tartozott hozzá annak vizsgálata, hogy léteznek-e a feltételeknek eleget tevő H halmazok. A megoldásból látszik ‐ hiszen k-nak egész számnak kell lennie ‐, hogy nem minden (m;n) párhoz van H. A létezés szükséges feltétele, hogy mn(n-1); általában azonban a létezés kérdése megoldatlan probléma. Az ábrákon két egyszerű példát mutatunk. H elemeit pontokkal (P1, P2, ...) jelöljük, a kitüntetett részhalmazok kételeműek, ezeket úgy adjuk meg, hogy a részhalmazt alkotó két pontot egy egyenessel összekötjük. Az m=n=3 esetén is létezik H (13 elemet tartalmaz, és 26 részhalmazt kell kijelölnünk), ennek megadása azonban már nem ilyen egyszerű.