Feladat: 1987. évi Kürschák matematikaverseny 3. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Benczúr András ,  Dinnyés Enikő ,  Drasny Gábor ,  Fleiner Tamás ,  Gács András ,  Keleti Tamás ,  Lengyel Csaba ,  Lipták László ,  Rimányi Richárd ,  Tasnádi Tamás 
Füzet: 1988/február, 56 - 59. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorika, Kombinációk, Binomiális együtthatók, Kombinatorikai leszámolási problémák, Számtani közép, Mértani közép, Egyenlőtlenségek, Gráfelmélet, Egyéb szinezési problémák, Teljesgráfok, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1988/február: 1987. évi Kürschák matematikaverseny 3. 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. Mindenki mindenkivel csak egyféle játékot játszik, hiszen mindenkinek 3n partnere van és összesen ennyi játszmában vesz részt.
Három embert összesen

(3n+13)
féleképpen lehet kiválasztani a társaságból. Számoljuk össze, hány olyan hármas lehet maximálisan, amelyiknek a tagjai legfeljebb kétféle játékot játszanak egymás közt! A társaság egy A tagja n emberrel pingpongozik, így (n2) olyan hármasban van benne, amelyiknek mind a két másik tagjával pingpongozik. Ugyanennyi olyan hármasban van benne, amelyikben mindkét partnerrel sakkozik, illetőleg amelyikben mindkettővel teniszezik, tehát 3⋅(n2) olyan hármas van, amelyikben ő csak egyféle játékot játszik. Ez igaz a társaság bármelyik tagjára, tehát az olyan hármasok száma, amelyeknek tagjai legfeljebb kétféle játékot játszanak egymás közt, nem több, mint
3(n2)(3n+1),
az olyan hármasokat ugyanis, ha vannak, amelyeken belül csak egyféle játékot játszanak, többször vettük számba. Az olyan hármasok száma tehát, amelyeken belül mind a három játékot játsszák, legalább
(3n+13)-3(n2)(3n+1)=(3n+1)3n(3n-1)6-3n(n-1)2⋅(3n+1)=3n2+n.
A feladat állítása tehát igaz.
 
Megjegyzés. A bizonyítás alsó korlátot is adott a feladat követelményeit kielégítő hármasok számára, nem adott viszont eljárást ilyen hármasok kiválasztására, csak létezésüket bizonyítja.
 
II. megoldás. A feladat állításának helyességét indirekt úton bizonyítjuk. Legyen A a társaság egy tagja, P azoknak a csoportja, akik A-val pingpongoznak, S azoké, akik sakkoznak vele és T az A-val teniszezőké. Tegyük fel, hogy nincs a feladat állításának megfelelő hármas. Ekkor egy P-beli és egy S-beli nem teniszezhet, egy S-beli és egy T-beli nem pingpongozhat, egy T-és egy P-beli pedig nem sakkozhat, mert különben A-val megfelelő hármast alkotnának.
Megszámoljuk kétféleképpen azoknak a hármasoknak a számát, amelyekben mindegyik csoportnak egy tagja szerepel. Mindegyik csoportból n-féleképpen választhatunk egy embert, tehát a lehetséges hármasok száma n3. Mivel egyik hármas tagjai sem játsszák mind a három játékot egymás közt, így valaki mindkét partnerével ugyanazt a játékot játssza. Egy ilyen hármas P-beli tagja mindkét partnerével csak pingpongot játszhat fenti megállapításaink szerint. Ha S-ből j emberrel pingpongozik, T-ből pedig k-val, akkor jk olyan hármasnak tagja, amelyiken belül két pingpongozó pár van. Egyrészt tudjuk, hogy összesen n pingpongpartnere van, így* j+k≤n, másrészt a mértani és számtani közép közti egyenlőtlenség szerint
jk≤(j+k2)2≤(n2)2.
Mivel a P csoportnak n tagja van, tehát legfeljebb n3/4 olyan hármas van, amelyikben két pingpongozó pár szerepel. Ugyanez igaz az olyan hármasok számára is, amelyekben két sakkozó, ill. amelyekben két teniszező pár szerepel. Ez azonban összesen is csak 3n3/4 hármast ad, kevesebbet, mint az összes tekintetbe vett hármasok száma. Indirekt feltevésünk tehát helytelennek bizonyult, kell olyan hármasnak lennie, amelyiknek tagjai mindegyik játékot játsszák egymás közt.
 
III. megoldás. Tekintsük ismét a társaságnak az előző megoldásban szereplő felbontását csoportokra. Becsüljük meg felülről azoknak a hármasoknak a számát, amelyekben szerepel A és amelyek nem felelnek meg a feladat állításában szereplő feltételnek. Csak olyan hármasok jönnek tekintetbe, amelyekben A-n kívül két különböző csoportbeli ember szerepel. Az ilyen hármasok száma 3n2. Azt is láttuk az előző megoldásban, hogy egy ilyen hármas akkor nem megfelelő, ha benne egy pingpongozó pár egyike P-ből való, vagy egy sakkparti egyik résztvevője S-ből, vagy egy teniszező pár egyike T-ből való. Egy P-beli P személy S-ből és T-ből együtt legfeljebb n-1 emberrel pingpongozik, mert egyik pingpongpartnere A. A tekintetbe vett hármasok közül azok száma, amelyekben a P-beli n ember valamelyike pingpongozik a harmadik társsal, legfeljebb n(n-1). Ugyanez mondható az olyan hármasok számáról, amelyekben egy S-beli egyén sakkozik a harmadikkal és azokéról, amelyekben olyan T-beli szerepel, aki teniszezik a harmadikkal. A 3n2 számba vett hármas közül tehát legfeljebb 3n2-3n az, amelyikre nem teljesül a feladat állítása; legalább 3n hármasra tehát teljesül.
 
Megjegyzések. 1. Ha a meggondolást a társaság mind a 3n+1 tagjára megismételjük, akkor minden számba jövő hármast háromszor veszünk tekintetbe. Ennek alapján a társaságból kiválasztható összes olyan hármasok száma, amelyekben mind a három játékot játsszák egymás közt, legalább n(3n+1). Ugyanazt a becslést nyertük, mint az első megoldásban. Szoros rokonságban is van a két megoldás, amennyiben az utóbbiban is olyan hármasok számának becslése útján jutottunk célhoz, amelyekben csak kétféle játékot játszanak.
A fenti megoldásban azokat a hármasokat vettük számba, amelyekben szerepel A, de a két társával ugyanazt a játékot játszó személy P-ben, S-ben, vagy T-ben van.
 
 
3.a ábra
 

 
 
3.b ábra
 

 
 
3.c ábra
 

2. A nyert korlát n=1, 2, 3, 4 esetén pontos. Ezt az első három esetben leolvashatjuk a 3.a, 3.b, 3.c ábrákról, amelyeken a pontok a társaság tagjait képviselik, a folytonos vonallal összekötöttek a pingpongozó párokat jelölik, a szaggatott vonalak a sakkpartikat, a pontozott összekötések pedig a teniszezőket. Az n=4 esetben a 13 embert körbe állítva mindenki a két szomszédjával és a harmadik szomszédjaival pingpongozik, a második és az ötödik szomszédjaival sakkozik, a negyedik és a hatodik szomszédjaival pedig teniszezik. Az ezt feltüntető ábrát bonyolultsága miatt jobb, ha az olvasó magának nagyban és esetleg színes vonalakkal rajzolja meg.
Nagyobb n-ekre már mindig nagyobb a megfelelő hármasok száma az itt nyert értéknél.*
 
IV. megoldás. Eljárást adunk egy kívánt tulajdonságú hármas megkeresésére. Ismét a társaság előző megoldásokban szereplő csoportosításából indulunk ki. A P csoport egy P1 tagja sakkozik másik csoportbeli emberrel, mert P-ben rajta kívül n-1 ember van, tehát ennél több sakkpartnere sem lehet. Ha van sakkpartnere T-ben, akkor azzal és A-val a feladat követelményének megfelelő hármast alkotnak. Ha nincs, akkor egy S-beli S1 sakkpartnerét véve, annak van teniszpartnere S-en kívül. Ha teniszezik P-beli társsal, akkor ismét megfelelő hármast alkotnak A-val. Ha nem, akkor egy T-beli T1 teniszpartnerről ismét feltehetjük, hogy T-n kívüli pingpongpartnerei P-ben vannak. Egyet kiválasztva az eljárást folytathatjuk, míg el nem jutunk vagy egy olyan párhoz, akik A-val együtt megfelelő hármast alkotnak, vagy olyan valakihez, aki már korábban is szerepelt. Utóbbi esetben egy kört kapunk, amelyikben egy-egy P-, S-, T-beli személy követi egymást periodikusan, és mindenki olyan játékot játszik a rákövetkezővel, amilyent az utóbbi A-val játszik. Ha ez a kör három emberből áll, akkor ők megfelelő hármast alkotnak.
Megmutatjuk, hogy ha a kör ennél hosszabb, akkor kihagyható belőle három egymás utáni ember úgy, hogy a kör leírt szerkezete megmaradjon, vagy találunk egy megfelelő hármast. Legyen S, T, P', S', T' a kör öt egymás utáni tagja. Ha P' és T' sakkozik, akkor A-val, ha pedig pingpongozik, akkor S'-vel alkotnak megfelelő hármast. Az az eset vizsgálandó tovább, ha teniszeznek. Ha P' és S teniszezik, akkor A-val, ha sakkoznak, akkor T-vel alkotnak megfelelő hármast; marad az az eset, ha pingpongoznak. Nézzük ekkor S-et és T'-t. Ha pingpongoznak, akkor A-val, ha sakkoznak, akkor a vizsgált esetben P'-vel alkotnak megfelelő hármast. Ha viszont S és T' teniszezik, akkor T, P' és S' kihagyása után is megmarad a kör föntebb leírt szerkezete. Így az eljárás véges számú ismétlésével eljutunk a feladat állításának megfelelő hármashoz.
 
Megjegyzések. 1. A társaság tagjait pontokkal, a köztük zajló különböző játékokat különböző fajta vonalakkal ábrázolva, ahogyan azt a 3. ábrán is tettük, gráf keletkezik. A vonalakat ‐ a gráf éleit ‐ megkülönböztethetjük különböző színek használatával. Az olyan gráfot, amelyikben minden pontot mindegyik másikkal összeköt egy él, teljes gráfnak nevezik. Gráfok nyelvén fogalmazva és csekély általánosítással a következő tételt nyerjük: Ha m≧3 és egy m szögpontú teljes gráf éleit 3 színnel színezzük úgy, hogy az egy-egy szögpontból induló különböző színű élek száma legfeljebb eggyel különbözzék, akkor van a gráfban olyan 3 pont, amelyeket különböző színű élek kötnek össze. A fenti megoldások az általánosabb esetben is célra vezetnek.
 
2. Láttuk, hogy az adott feltételek mellett nem csak létezik kívánt tulajdonságú hármas, de elég szép számban van. Kérdés, hogy nem lazíthatnánk-e a színeloszlás egyenletességének követelményén úgy, hogy a következmény még érvényes legyen. Nem elegendő-e például azt megkívánni, hogy bármelyik pontból induló egyszínű élek száma legalább az összes élek 0,3 része legyen?
Annyi biztos, hogy ez az arányszám nem vihető 1/4 alá. Ez így látható be: vegyünk 4, egyenként n pontból álló ponthalmazt. Az egy halmazon belüli élek legyenek pirosak, azok, amelyek első és második halmazbeli pontokat vagy harmadik és negyedik halmazbelieket kötnek össze, kékek, a többi él legyen zöld. Ekkor minden pontból n-1 piros él indul ki, n kék és 2n zöld, és könnyen látható, hogy nincs háromszínű háromszög. Felmerül a kérdés, hol van a kritikus határ 1/3 és 1/4 közt. Lapzártakor értesültünk, bizonyítást nyert, hogy az 1/4 érték az.
*Valójában j+k≤n-1 is fennáll, mert az illető egyik pingpongpartnere A.

*Erre a kérdésre lapunkban visszatérünk (szerk.).