Feladat: 1964. évi Kürschák matematikaverseny 2. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Corradi Gábor ,  Gerencsér László ,  Lovász László ,  Makai Endre 
Füzet: 1965/március, 101 - 104. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorika, Kombinatorikai leszámolási problémák, Logikai feladatok, Gráfelmélet, Páros gráfok, Teljesgráfok, Egyéb szinezési problémák, Teljes indukció módszere, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1965/március: 1964. évi Kürschák matematikaverseny 2. feladata

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.

I. megoldás. A fiúkat osztályozhatjuk aszerint, hogy ki hány lánnyal táncolt. Tartozzék F1 azok közé a fiúk közé, akik a legtöbb lánnyal táncoltak. Minthogy F1 sem táncolt minden lánnyal, van olyan L1 lány, akivel F1 nem táncolt. Van viszont olyan F2 fiú, aki táncolt L1-gyel, hiszen L1 is táncolt legalább egy fiúval.
F1 megválasztása miatt F2 nem táncolhatott több lánnyal, mint ahánnyal F1 táncolt. Ebből következik, hogy F2 nem táncolhatott mindazokkal a lányokkal, akikkel F1 táncolt, mert az ellenkező esetben F2 több lánnyal táncolt volna, mint F1, hiszen F2 táncolt L1-gyel is, F1 pedig nem. Van tehát olyan L2 lány, akivel F1 táncolt, de F2 nem.
Az F1, F2 fiúk és L1, L2 lányok kielégítik a feladat követelményét, hiszen F1 és L1, valamint F2 és L2 nem táncoltak egymással, viszont F1 táncolt L2-vel és F2 táncolt L1-gyel.

 
Megjegyzés. A feladat feltevései közül csak azt használtuk fel, hogy egyik fiú sem táncolt minden lánnyal, s hogy minden lány táncolt legalább egy fiúval. Ugyanígy persze elég lett volna csak arra támaszkodnunk, hogy egyik lány sem táncolt minden fiúval, s hogy minden fiú táncolt legalább egy lánnyal, hiszen a fiúk és a lányok szerepét a megoldásban is felcserélhetjük. Két lehetőséget találtunk tehát a feladat szövegének módosítására, feltevéseinek gyengítésére.
Bár közvetlenebb és egyszerűbb megoldást nem tudunk adni, mégis ismertetünk további megoldásokat, mert ezek révén további érdekes kapcsolatokra és általánosításokra mutathatunk rá. Az előző bekezdés észrevétele a további megoldásokra is vonatkozik.
 
II. megoldás. Válasszunk ki a résztvevők közül egy F1 fiút és egy L1 lányt, akivel F1 nem táncolt. Legyen továbbá F2 olyan fiú, aki táncolt L1-gyel, és L2 olyan lány, akivel F2 nem táncolt. Ezt a kiválasztást ugyanígy folytatjuk: Fi kiválasztása után (i=2,3,...) olyan Li lányt választunk, akivel Fi nem táncolt, majd olyan Fi+1 fiút, aki táncolt Li-vel. Addig folytatjuk ezt, amíg nem kerülne sor olyannak a kiválasztására, akit korábban már kiválasztottunk. Minthogy a táncmulatságon véges sokan vesznek részt, ez előbb-utóbb bekövetkezik. Eszerint ki lehet választani k fiút és k lányt, és ezeket körbe lehet úgy állítani, hogy minden fiút két lány fogjon közre, és minden fiú táncolt a balján álló lánnyal, de nem táncolt a jobbján állóval. Azt kell bebizonyítanunk, hogy ez már két fiúval és két lánnyal is megvalósítható.
Legyenek egy ilyen körben állók sorjában
F1,L1,F2,L2,...,Fk,Lk,
ahol tehát azt is tudjuk, hogy F1 és Lk táncoltak egymással. Megmutatjuk, hogy ha k>2, akkor kevesebb fiúból és lányból is tudunk ilyen kört alkotni. Ha ugyanis F1 táncolt L2-vel, akkor
F1,L1,F2,L2,
ha pedig F1 nem táncolt L2-vel, akkor
F1,L2,...,Fk,Lk
elégíti ki a követelményt. Eszerint a létszám mindig tovább csökkenthető, amíg csak két fiúhoz és két lányhoz el nem jutunk.
 
Megjegyzés. Ha a résztvevőket pontokkal ábrázoljuk, és az egymással táncolókat ábrázoló pontokat egy-egy vonallal kötjük össze, egy gráf szögpontjaihoz és éleihez jutunk. Ha a vonalak esetleg metszik egymást, metszéspontjukat nem mondjuk a gráf szögpontjának.
A kapott gráfot páros gráfnak mondjuk, mert szögpontjai két osztályba sorolhatók (ti. a fiúkat és a lányokat ábrázoló szögpontokéba) olyan módon, hogy minden él két más-más osztályba tartozó szögpontot köt össze. Kiegészíthetjük ezt a gráfot azáltal, hogy éllel kötünk össze minden más-más osztályba tartozó két szögpontot. Ennek az élei tehát kétfélék: vagy szerepeltek már az eredeti gráfban is, vagy csak utóbb csatoltuk hozzá. Ezt a kétféleséget azzal szemléltethetjük, hogy az éleket két színnel színezzük meg.
Mondhatjuk tehát, hogy feladatunk egy két színnel megfestett teljes páros gráfról szól. Bármelyik szögpontot tekintjük is, a belőle kiinduló élek a feladat feltevése szerint nem mindannyian ugyanolyan színűek. A feladat már bebizonyított állítása szerint található az ilyen gráfban négy csatlakozó él által alkotott ,,négyszög'', amelynek az élei váltakozva más-más színűek.
Ez az átfogalmazás már a bizonyítás során is alkalmazható lett volna. Az olvasóra hagyjuk, hogy ezt a valamivel szemléletesebb megfogalmazást végiggondolja. Felhívjuk azonban a figyelmet arra, hogy a két szín között nincs semmiféle szerepkülönbség. Ez annak felel meg, hogy eredeti feladatunk tartalma mit sem változik, ha benne az ,,egymással táncolt'' és ,,egymással nem táncolt'' fogalmakat felcseréljük. Ha másodszor is összegyűlnek a résztvevők, de most csak azok táncolnak egymással, akik az első alkalommal nem táncoltak, akkor is ugyanazok elégítik ki a feladat állításának követelményeit.
Megoldásunk gondolatmenete változatlanul alkalmazható akkor is, ha nem teljes páros gráfról; hanem teljes gráfról beszélünk, azaz olyanról, amelyben minden szögpontpárt él köt össze. Ennek az ellenőrzését is az olvasóra hagyjuk. Megelégszünk azzal, hogy az így bizonyított állítást a következő szemléletes alakban adjuk elő: Egy társaságban egyesek ismerik egymást, mások nem; senki sem ismer mindenkit, de mindenkinek van ismerőse a társaságban; kiválasztható akkor a társaság négy tagja, s ezek leültethetők egy kerek asztal köré úgy, hogy két szomszédja közül mindenki csak az egyiket ismerje. Ehhez az eredményhez az első megoldás módszerével is könnyen eljuthattunk volna.
 
III. megoldás. Feltesszük, hogy a táncmulatság résztvevői közül nem választhatók ki négyen a követelményt kielégítő módon, s ebből a feltevésből ellentmondásra következtetünk, ti. arra, hogy akkor a táncmulatságnak végtelen sok résztvevője van. Ezáltal a feladat állításának helyességét bizonyítjuk be.
Legyen L1 az egyik lány és F1 olyan fiú, aki táncolt L1-gyel. Legyen L2 olyan lány, aki nem táncolt F1-gyel, és F2 olyan fiú, aki táncolt L2-vel. Megállapíthatjuk, hogy F2 táncolt L1-gyel, mert különben (L1, F1, F2) kielégítené a feladat követelményét. Az eddig említett résztvevők közül eszerint csak L2 és F1 nem táncoltak egymással.
Tegyük fel, hogy már találtunk olyan
L1,F1,L2,F2,...,Lk,Fk
résztvevőket, akik közül ketten csak akkor nem táncoltak, ha a lány indexe a fiúénál nagyobb. Ez volt a helyzet k=2 esetében. Megmutatjuk most, hogy a sorozat kiegészíthető Lk+1, Fk+1 résztvevőkkel olyan módon, hogy a kiegészített sorozat is rendelkezzék az eredeti sorozat tulajdonságával. Ebből majd valóban következik, hogy a kiegészítés minden határon túl folytatható, hogy tehát végtelen sok résztvevő van.
Minthogy Fk táncolt az L1,...,Lk lányok mindegyikével, van olyan további Lk+1 lány, akivel nem táncolt. Ez az Lk+1 lány nem táncolt az F1,...,Fk-1 fiúkkal sem, pl. Fi-vel azért, mert különben (Lk, Fk, Lk+1, Fi), kielégítené a követelést. Minthogy Lk+1 nem táncolt az F1,...,Fk fiúk egyikével sem, van olyan további Fk+1 fiú, akivel táncolt. Ez az Fk+1 fiú táncolt az L1,...,Lk lányokkal is, pl. Li-vel azért, mert az ellenkező esetben (Li, Fi, Lk+1, Fk+1) kielégítené feladatunk követelését. Ezek szerint a kiegészített
L1,F1,L2,F2,...,Lk,Fk,Lk+1,Fk+1
sorozat valóban rendelkezik azzal a tulajdonsággal, hogy egy sorozatbeli lány és fiú csak akkor nem táncolt egymással, ha kettejük indexe közül a lányé a nagyobb.
 
Megjegyzés. Megoldásunk arra is rámutatott, hogy a feladat állítása végtelen sok résztvevő, pontosabban végtelen sok fiú és végtelen sok lány részvétele esetén már nem helyes. Egy ellenpéldát, talán még mindig szemléletesen, a következőképpen adhatunk elő: Egy végtelen nagy társaságban senkinek a magassága sem éri el a 180cm-t, de bármily kevéssel kisebb magasságot adunk is meg, már található olyan fiú is és olyan lány is, aki azt a magasságot eléri; minden fiú csak a nála kisebb lányokkal táncol. Könnyű ellenőrizni, hogy ekkor a feladat feltevései teljesülnek, viszont nem választható ki két fiú és két lány a feladat követelményét kielégítő módon.
Ez az ellenpélda természetesen megszövegezhető úgy is, hogy csak gráfokról szólunk. Felvetjük most a megfelelő kérdést végtelen teljes gráfokra is. Kérdezzük tehát, hogy ha egy végtelen sok szögpontú teljes gráf éleit úgy színezzük meg két színnel, hogy egy szögpontból se induljon ki csupa ugyanolyan színű él, vajon mindig igaz-e, hogy a gráf tartalmaz váltakozó színű négyszöget. Olyan példát adunk meg, amely mutatja, hogy ez sem igaz. Tartozzék a természetes számok mindegyikéhez egy-egy szögpont; az a, b számokhoz tartozó szögpontokat összekötő él legyen piros vagy kék aszerint, hogy a és b nagyobbika páros-e vagy páratlan. Könnyű ellenőrizni, hogy itt a feltételek teljesülnek, viszont váltakozó színű négyszög nem található.
 
IV. megoldás. Tudjuk, hogy minden fiúhoz található olyan lány, akivel nem táncolt. Lehetséges, hogy bármely két fiúhoz is található olyan, akivel egyikük sem táncolt. Talán bármely három vagy esetleg még több fiúhoz is található mindig ilyen lány. Van mindenesetre egy legnagyobb k érték, amelyre még igaz, hogy bármely k fiúhoz található olyan lány, akivel egyikük sem táncolt. Ez a k kisebb, mint a táncmulatságon résztvevő fiúk száma, hiszen minden lány táncolt legalább egy fiúval.
Minthogy k+1 már nem rendelkezik k tulajdonságával, kiválasztható k+1 fiú:
F1,F2,...,Fk+1
olyan módon, hogy minden lány táncolt valamelyikükkel. Ha közülük egyet, pl. F1-et elhagyjuk, a megmaradó k fiúhoz k tulajdonsága miatt található olyan L1 lány, akivel egyikük sem táncolt, s ezért vele a k+1 fiú közül csak F1 táncolt. Ugyanígy okoskodhatunk, ha a k+1 fiú közül nem F1-et, hanem egy másikat hagyunk el. Ilyen módon olyan
L1,L2,...,Lk+1
lányokhoz jutunk, akiknek mindegyike csak az ugyanolyan indexű fiúval táncolt a k+1 fiú közül.
Minthogy k≥1, az F1, F2 fiúkról és az L1, L2 lányokról minden esetben szó lehet, s ezek kielégítik a feladat követelményét.
 
Megjegyzés. Valamivel rövidebb volna ez a megoldás, ha befejezésekor csak L1 és L2 létezésére következtetnénk, hiszen csak erre volt szükség. Így viszont a következő, a feladat állításánál többet mondó eredményhez is eljutottunk: Ha egy táncmulatságon minden lány táncol legalább egy fiúval, és bármely k fiúhoz található olyan lány, akivel egyikük sem táncolt, akkor kiválasztható a résztvevők közül k fiú és k lány úgy, hogy ezek mindegyike táncolt ezek valamelyikével, mégpedig mindenki csak eggyel.
Megoldásunk gondolatmenete ismét alkalmazható akkor is, ha nem egy teljes páros gráf, hanem egy teljes gráf két színnel való megszínezéséről van szó. Az olvasó könnyen ellenőrizheti, hogy így a következőképpen megfogalmazható eredményhez jutunk: Egy társaságban mindenkinek van ismerőse, de a társaság bármely k tagjához található olyan, akit egyikük sem ismer; ekkor kiválasztható a társaságnak 2k tagja, s ezek leültethetők egy asztal két oldalán olyan módon, hogy a szemközti oldalon ülők közül mindenki csak a vele szemben ülőt ismerje.