|
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 partnere van és összesen ennyi játszmában vesz részt. Három embert összesen 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 tagja emberrel pingpongozik, így 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 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 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 | | 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 társaság egy tagja, azoknak a csoportja, akik -val pingpongoznak, azoké, akik sakkoznak vele és az -val teniszezőké. Tegyük fel, hogy nincs a feladat állításának megfelelő hármas. Ekkor egy -beli és egy -beli nem teniszezhet, egy -beli és egy -beli nem pingpongozhat, egy -és egy -beli pedig nem sakkozhat, mert különben -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 -féleképpen választhatunk egy embert, tehát a lehetséges hármasok száma . 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 -beli tagja mindkét partnerével csak pingpongot játszhat fenti megállapításaink szerint. Ha -ből emberrel pingpongozik, -ből pedig -val, akkor olyan hármasnak tagja, amelyiken belül két pingpongozó pár van. Egyrészt tudjuk, hogy összesen pingpongpartnere van, így , másrészt a mértani és számtani közép közti egyenlőtlenség szerint Mivel a csoportnak tagja van, tehát legfeljebb 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 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 és amelyek nem felelnek meg a feladat állításában szereplő feltételnek. Csak olyan hármasok jönnek tekintetbe, amelyekben -n kívül két különböző csoportbeli ember szerepel. Az ilyen hármasok száma . Azt is láttuk az előző megoldásban, hogy egy ilyen hármas akkor nem megfelelő, ha benne egy pingpongozó pár egyike -ből való, vagy egy sakkparti egyik résztvevője -ből, vagy egy teniszező pár egyike -ből való. Egy -beli személy -ből és -ből együtt legfeljebb emberrel pingpongozik, mert egyik pingpongpartnere . A tekintetbe vett hármasok közül azok száma, amelyekben a -beli ember valamelyike pingpongozik a harmadik társsal, legfeljebb . Ugyanez mondható az olyan hármasok számáról, amelyekben egy -beli egyén sakkozik a harmadikkal és azokéról, amelyekben olyan -beli szerepel, aki teniszezik a harmadikkal. A számba vett hármas közül tehát legfeljebb az, amelyikre nem teljesül a feladat állítása; legalább hármasra tehát teljesül.
Megjegyzések. 1. Ha a meggondolást a társaság mind a 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 . 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 , de a két társával ugyanazt a játékot játszó személy -ben, -ben, vagy -ben van.
3.a ábra
3.b ábra
3.c ábra 2. A nyert korlát , , , 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 esetben a 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 -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 csoport egy tagja sakkozik másik csoportbeli emberrel, mert -ben rajta kívül ember van, tehát ennél több sakkpartnere sem lehet. Ha van sakkpartnere -ben, akkor azzal és -val a feladat követelményének megfelelő hármast alkotnak. Ha nincs, akkor egy -beli sakkpartnerét véve, annak van teniszpartnere -en kívül. Ha teniszezik -beli társsal, akkor ismét megfelelő hármast alkotnak -val. Ha nem, akkor egy -beli teniszpartnerről ismét feltehetjük, hogy -n kívüli pingpongpartnerei -ben vannak. Egyet kiválasztva az eljárást folytathatjuk, míg el nem jutunk vagy egy olyan párhoz, akik -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 -, -, -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 -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 , , , , a kör öt egymás utáni tagja. Ha és sakkozik, akkor -val, ha pedig pingpongozik, akkor -vel alkotnak megfelelő hármast. Az az eset vizsgálandó tovább, ha teniszeznek. Ha és teniszezik, akkor -val, ha sakkoznak, akkor -vel alkotnak megfelelő hármast; marad az az eset, ha pingpongoznak. Nézzük ekkor -et és -t. Ha pingpongoznak, akkor -val, ha sakkoznak, akkor a vizsgált esetben -vel alkotnak megfelelő hármast. Ha viszont és teniszezik, akkor , é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 és egy szögpontú teljes gráf éleit 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 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 része legyen? Annyi biztos, hogy ez az arányszám nem vihető alá. Ez így látható be: vegyünk , egyenként 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 piros él indul ki, kék és 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 és közt. Lapzártakor értesültünk, bizonyítást nyert, hogy az érték az. Valójában is fennáll, mert az illető egyik pingpongpartnere .Erre a kérdésre lapunkban visszatérünk (szerk.). |
|