Feladat: Gy.3106 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Andrássy Zoltán ,  Babos Attila ,  Balogh Attila ,  Benedek Csaba ,  Bérces Márton ,  Bosznay Tamás ,  Csikvári Péter ,  Csirmaz Előd ,  Csiszár Gábor ,  Dancsó Zsuzsanna ,  Davidovics Gábor ,  Deli Lajos ,  Földényi Tamás ,  Gelencsér Gábor ,  Gueth Krisztián ,  Gyenes Zoltán ,  Győri Nikolett ,  Györey Bernadett ,  Hangya Balázs ,  Horváth Gábor ,  Kajtár Márton ,  Keszegh Balázs ,  Kiss Gergely ,  Kutalik Péter ,  Lengyel Tímea ,  Mecz Balázs ,  Miklós Levente ,  Naszódi Gergely ,  Papp Dávid ,  Reviczky Ádám ,  Schlotter Ildikó ,  Schmidt Ákos ,  Schmidt András ,  Szabadka Zoltán ,  Szalontay Mihály ,  Szentes Szilvia ,  Taraza Busra ,  Terpai Tamás ,  Tillinkó Zsanett ,  Vaik István ,  Varga Szilvia ,  Varjú Péter ,  Végh László ,  Venter György ,  Wilfing András ,  Zábrádi Gergely 
Füzet: 1997/október, 410 - 411. oldal  PDF  |  MathML 
Témakör(ök): Halmazelmélet, Részhalmazok, Gyakorlat
Hivatkozás(ok):Feladatok: 1997/január: Gy.3106

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.

Jelöljük a halmaz elemeinek számát n-nel. Ekkor a halmaz kételemű részhalmazainak a száma (n2)=n(n-1)2. Egy kijelölt 3 elemű részhalmaz pontosan 3 db kételemű részhalmazt tartalmaz, így a 7 db háromelemű részhalmaz összesen 7⋅3=21 különböző kételemű részhalmazt tartalmaz. Ezért n(n-1)2=21, amiből (n>0 mellett) n=7 adódik. Tehát a halmaznak 7 eleme van. (Ha a halmaz elemeit 1, 2, 3, 4, 5, 6, 7 jelöli, akkor egy lehetséges példa a hét darab részhalmazra: {1, 2, 3}; {1, 4, 5}; {1, 6, 7}; {2, 4, 6}; {2, 5, 7}; {3, 4, 7}; {3, 5, 6}. Ugyanezt a példát szemlélteti az ábra, ahol a halmaz elemei a számmal jelölt pontok, a kijelölt részhalmazok pedig a berajzolt egyenesek és a kör mentén lévő pontok által alkotott részhalmazok.)

 
 

Megmutatjuk, hogy legfeljebb 4 részhalmazt tudunk a feltételeknek megfelelően kiválasztani. Ha 5 részhalmazt választunk, akkor ezekben ‐ multiplicitással számolva ‐ összesen 5⋅3=15 elem van. Mivel 15>2⋅7, azért a 15 közt van legalább 1 elem, amely (legalább) háromszor fordul elő, azaz 5 részhalmaz közt biztosan van 3, amely tartalmazza ugyanazt az elemet. 4 részhalmazt viszont mindig ki tudunk választani: rögzítsük a halmaz egyik elemét, jelöljük ezt 1-gyel. Ezt az elemet a feltételek miatt pontosan 7-13-1=3 kijelölt részhalmaz tartalmazza. Megmutatjuk, hogy a maradék 7-3=4 kijelölt részhalmaz közül semelyik 3 sem tartalmazza ugyanazt az elemet. Ha ugyanis ezek közt lenne 3, amelyik tartalmazná ugyanazt az elemet, akkor e 3 részhalmaz többi, összesen 3(3-1)=6 elemének mind különbözőnek kellene lenni, ezért egyikük tartalmazná 1-et is, ami ellentmondás. (Előző példánk esetén a 4 részhalmaz: {2, 4, 6}; {2, 5, 7}; {3, 4, 7} és {3, 5, 6}.)
Összefoglalva: tehát a halmaznak 7 eleme van, és mindig legfeljebb 4 részhalmazt tudunk a feltételeknek megfelelően kiválasztani.