Feladat: 3.15.
* Újra felkeressük a K.II.19.32. feladat 3n+1 tagú társaságot, amelynek bármely két tagja vagy teniszezni, vagy sakkozni, vagy pingpongozni szokott egymással. Mindegyiküknek n tenisz-, n sakk- és n pingpongpartnere van. A feladat megoldásában láttuk, hogy a társaság tagjaiból legalább (3n+1)n olyan hármas állítható össze, amelyek egymás között mind a három játékot játsszák. Azt is láttuk, hogy ez nagy n-ekre elenyészően csekély, 2/(3n-1)-ed része az összes hármasnak. Vajon javítható-e az ottani eredményünk? Van-e olyan pozitív c szám, amelyre igaz, hogy a társaság tagjaiból kiválasztható legalább c( 3n+1 3 )-féleképp három úgy, hogy azok egymás között mind a három játékot játsszák (vagyis a hármasoknak legalább a c-ed része ,,tarka" hármas ebben az értelemben)?
 

Megoldás: 3.15
A kényelem kedvéért fogalmazzuk át a feladatot gráfokra. Adott egy 3n+1 pontú teljes gráf, amelynek éleit három színnel, T-vel, P-vel és S-sel úgy, hogy minden csúcsból, az onnan kiinduló élek közül ugyanannyi ( n) él lesz T, P és S színű. Az a kérdés, hogy legalább hány ,,tarka" hármast tudunk garantálni, azaz olyat, amelyekben mind a három szín szerepel.

Jelöljük a ,,tarka" háromszögek számát H3 , az egyszínűekét (tehát ahol mind a három él azonos színű) H1 és az olyanokét, amelyekben két szín szerepel, H2 . Vezessük be a ,,cseresznye" fogalmát. Ez két, egy csúcsból induló élből álló alakzat. Ha megszámoljuk kétféleképpen, hogy hány egyszínű cseresznye van, akkor azt kapjuk, hogy

3 H1 + H2 =(3n+1)3n(n-1)/2

,

hiszen egy egyszínű háromszögben három, egy kétszínűben egy egyszínű cseresznyét találunk; másrészt minden csúcsban minden színből ( n 2 )-t.

Ha összeszámoljuk kétféleképpen, hogy hány kétszínű cseresznye van, akkor viszont azt kapjuk, hogy

2 H2 +3 H3 =(3n+1)3 n2

,

hiszen egy kétszínű háromszögben két kétszínű cseresznye van, egy háromszínűben pedig három. Másrészt egy csúcsból induló cseresznyék közül például T és P színű cseresznyéből n2 van, és három ilyen színpárosítás lehetséges.

Ha most a második eredményből kivonjuk az első kétszeresét és osztunk hárommal, akkor átrendezés után azt kapjuk, hogy

H3 =(3n+1)n+2 H1

.

Ez az eredmény máris több, mint a K.II.19.32. feladat megoldásánál kapott (3n+1)n becslés. Persze, még mindig kevés, a feladat most úgy módosult, hogy most már az egyszínű háromszögekről kell belátnunk, hogy az összes háromszög pozitív százalékát adják nagy n-re is. Itt megkérdezhetnénk, hogy miért jobb nekünk, hogy H1 -et kell megbecsülnünk, mint az eredeti feladat, ahol H3 -at kellett becsülnünk. Erre elég érdekes válasz adható, s ezt a 3.14. feladat tartalmazza: ha egy m csúcsú teljes gráf éleit három színnel színezzük, akkor még ha kikötjük is, hogy mind a három színt használni kell, akkor sem biztos, hogy lesz benne háromszínű háromszög. Viszont egyszínű biztosan lesz benne, ha m legalább 17 - ezt . feladatban láttuk. Tehát van rá reményünk, hogy könnyítettünk a helyzetünkön. És valóban: a 3.13. feladat szerint egy ilyen színezésben a hármasoknak legalább a 680-ad része egyszínű! Tehát 3n+1>17, azaz n>6 esetén már kész is vagyunk: beláttuk, hogy a mi esetünkben a ,,tarka", azaz háromszínű háromszögek száma legalább 340-ed része az összes hármasnak. n kisebb értékeire az állítás abból következik, hogy már (3n+1)n is több, mint 340-ed része az összes hármasnak ( 2/(3n-1)>1/340, ha n<227 - eredményünk csak ilyen n-ekre jobb, mint amit a K.II.19.32. feladat megoldásánál bizonyítottunk. Megjegyzés. A 340-es konstans javítható. Erről részletesebben lásd a KöMaL 1988/8-9. számában Surányi László: Megjegyzések az 1987. évi Kürschák József matematikai tanulóverseny 3. feladatához. című cikkét.