Feladat: F.3248 Korcsoport: 14-15 Nehézségi fok: átlagos
Megoldó(k):  Boros M. Mátyás ,  Csirmaz Előd ,  Csiszár Gábor ,  Csóka Endre ,  Dancsó Zsuzsanna ,  Dénes Attila ,  Devecsery András ,  Fehér Lajos Károly ,  Gelencsér Gábor ,  Gerencsér Balázs ,  Győri Nikolett ,  Gyürki István ,  Györey Bernadett ,  Harangi Viktor ,  Horváth Gábor ,  Horváth György ,  Keszegh Balázs ,  Kiss Gergely ,  Kunszenti-Kovács Dávid ,  Lábó Eszter ,  Lábó Melinda ,  Máthé András ,  Naszódi Gergely ,  Pálvölgyi Dömötör ,  Pap Júlia ,  Papp Dávid ,  Pozsonyi Gergő ,  Szabadka Zoltán ,  Szabó Péter ,  Szécsi Vajk ,  Taraza Busra ,  Terpai Tamás ,  Tran Thanh Long ,  Vágvölgyi Péter ,  Zábrádi Gergely 
Füzet: 1999/október, 411 - 412. oldal  PDF file
Témakör(ök): Gráfelmélet, Skatulyaelv, Feladat
Hivatkozás(ok):Feladatok: 1998/október: F.3248

Egy 5 lányból és 5 fiúból álló társaság azonos nemű tagjai nem ismerik egymást, továbbá nincs két olyan lány, akinek lenne két közös fiúismerőse. Legfeljebb hány ismeretség van a társaság tagjai között? Hogyan módosul a válasz, ha a társaságban 7 lány és 7 fiú van?

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 5 fiú és 5 lány esetén az ismeretségek száma legfeljebb 12. Tegyük fel, hogy ez nem igaz, a tagok közt legalább 13 ismeretség van. Ekkor a skatulya-elv alapján van 2 lány, akik együttvéve legalább 6 fiút ismernek. Ennél több fiút viszont nem is ismerhetnek, hiszen 5 fiú van, és ezek közül legfeljebb egyet ismernek mindketten. Tehát van 2 lány, akik együtt 6 ismeretséggel rendelkeznek, minden fiút ismer valamelyikük, egyet pedig mindketten. Ekkor viszont a többi lánynak fejenként legfeljebb 2 ismerőse lehet, egy a fenti lányok közül az egyik, egy pedig a másik fiúismerősei közül, különben valamelyiküknek 2 közös ismerőse lenne. Így az 5 lánynak összesen legfeljebb 6+32=12 ismerőse van, ami ellentmond a feltevésünknek.
Az 1. ábrán látható, hogy 12 ismeretség viszont már lehetséges a feltételeknek megfelelő módon. A lányokat az L1, L2, ..., L5, a fiúkat az F1, F2, ..., F5 pontok jelképezik, a társaság két tagja pedig pontosan akkor ismeri egymást, ha a megfelelő pontok össze vannak kötve.
Megmutatjuk, hogy 7 lány és 7 fiú esetén az ismeretségek száma legfeljebb 21. Tegyük fel, hogy ennél több. Ekkor a skatulya-elv alapján van egy lány, akinek legalább 4 ismerőse van. Ha egy másik lánnyal együtt valamennyi fiút ismerik, akkor ketten együtt legfeljebb 8 ismeretséggel rendelkeznek, a többiek pedig az előző esetekben is alkalmazott gondolatmenet szerint egyenként legfeljebb kettővel, vagyis az összes ismeretségek száma legfeljebb 8+52=18, ami ellentmondás. Nincs tehát olyan lány, aki az első lány által nem ismert ,,szabad'' fiúk mindegyikét ismerné.
Ekkor viszont csak úgy jöhet létre 22 ismeretség, ha az első lány pontosan 4 fiút ismer, a többi lány mindegyike pedig 2-2 szabad fiút, valamint az első lány ismerősei közül 1-1 fiút ismer. (22=4+63, 22-nél több ismeretség nem jöhet létre.) Ez azt jelenti, hogy a 6 lány közt biztosan van kettő, akiknek van közös ismerőse az első lány által ismert 4 fiú között (ismét a skatulya-elvet használtuk, 6>4). De ez a két lány a 3 szabad fiú közül 2-2-t ismer, tehát a szabad fiúk közt is van közös ismerősük, ami ellentmond a feladat feltételeinek. Tehát az ismeretségek száma valóban legfeljebb 21.
Azt, hogy 21 ismeretség elérhető, a 2. ábrán látható táblázat mutatja. A sorok a lányokat, az oszlopok a fiúkat jelképezik, egy sor és egy oszlop kereszteződésébe pontosan akkor írtunk 1-est, ha a megfelelő fiú és lány ismeri egymást.

 Dancsó Zsuzsanna (Budapest, ELTE Trefort Á. Gyak. Isk., 12. o.t.)

 
Megjegyzések. 1. Meg lehet mutatni, hogy 21 ismeretség csak úgy jöhet létre a feltételeknek megfelelő módon, ahogyan azt példánkban megadtuk (azaz a fiúkat és a lányokat megszámozhatjuk úgy, hogy az ismeretségek éppen a táblázatban megadottak legyenek).
2. Feladatunk tulajdonképpen egy gráfelméleti szélsőérték-probléma két speciális esetével foglalkozik. A probléma a következő:
Legfeljebb hány éle lehet egy olyan páros gráfnak, amelynek mind csúcshalmazában n csúcs van, és nem tartalmaz négyszöget?
A feladat megoldása megtalálható pl. Reiman István: A geometria és határterületei című könyvének 334‐336. oldalain. Általában igaz, hogy az élek száma legfeljebb (n+4n3-3n2)/2, s ez a korlát csak akkor érhető el, ha létezik ún. q-adrendű véges projektív sík, ahol n=q2+q+1.