Feladat: B.3662 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Bednay Dezső ,  Bereczki Péter ,  Birkus Róbert ,  Bősze Botond ,  Csajbók Bence ,  Czank Tamás ,  Dudás László ,  Erdélyi Márton ,  Estélyi István ,  Fehér Gábor ,  Gehér György ,  Gyarmati Ákos ,  Hegyháti Máté ,  Herczegh Péter ,  Hubai Tamás ,  Kecskeméti Szabolcs ,  Kiss-Tóth Christián ,  Kovács Dóra Judit ,  Kurgyis Zsuzsanna ,  Mátyás Péter ,  Mészáros Gábor ,  Molnár András ,  Nagy Csaba ,  Pálinkás Csaba ,  Sándor Ágnes Petra ,  Stippinger Marcell ,  Szilágyi Dániel ,  Török Zoltán Bálint 
Füzet: 2004/május, 280 - 283. oldal  PDF file
Témakör(ök): Klasszikus valószínűség, Feladat
Hivatkozás(ok):1951/december: Egyenlőtlenségek (4)
Feladatok: 2003/október: B.3662, 1951/november: 339. matematika feladat

Van egy zsebrádiónk, amely két ceruzaelemmel működik. A fiókban van 8 ceruzaelemünk, közülük 4 ki van merülve. A jó és rossz elemek sajnos összekeveredtek. Az elemek tesztelésére nincs más lehetőségünk, mint hogy belehelyezünk kettőt a készülékbe, és ha az szól, akkor mindkét elem jó, ha nem szól, akkor legalább az egyik rossz. Legalább hány kísérletre van szükség ahhoz, hogy biztosan megszólaljon a rádió?
 

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. Bebizonyítjuk, hogy hét kísérlet elegendő, annál kevesebb pedig nem.
Osszuk a nyolc elemet két darab hármas és egy kettes csoportba. Ekkor a három csoport között van olyan, amely a négy jó elem közül legalább kettőt tartalmaz, így ha az egyes csoportokon belül minden lehetőséget megvizsgálunk, akkor találunk üzemképes párost. Egy hármas csoport teszteléséhez három, a ketteséhez pedig egyetlen próba szükséges, így összesen legfeljebb 3+3+1=7 kísérlet után sikerrel járunk.
Nézzük meg, mi történhet hat vizsgálat során. Ekkor összesen 62=12 elemet helyezünk a rádióba, egyeseket természetesen többször is. Ha van olyan elem ‐ jelöljük A-val ‐, amelyet legalább háromszor próbálunk ki, akkor alakulhatnak úgy a kísérletek, hogy mind a hat megvizsgált párosnak hibás az egyik tagja, három esetben az A, a további háromban pedig a megmaradt három hibás elem valamelyike.
Ha egyetlen elem sem kerül kettőnél többször a rádióba, akkor ez csak úgy lehetséges, ha legalább négy elemet kétszer is kipróbálunk. A hat elvégzett kísérlet között azonban kell legyen olyan is, amelynek egyik résztvevője nem ilyen. Ha ugyanis csak ezekkel próbálkozunk és történetesen mind a négyük hibás, akkor a rádió a hatodik kísérlet után sem szólal meg. E négy elem között tehát van olyan pár, mondjuk A és B, amelyeket nem próbálunk ki együtt, hiszen a négy elemből összesen (42)=6 pár alkotható. Ha pedig A és B hibásak, akkor a rádió néma marad abban a négy kísérletben, amelyekben A és B vesznek részt, a további két kísérlet pedig alakulhat úgy, hogy mindegyikükben a másik két hibás elem egyike akad a kezünkbe.
Ezzel bebizonyítottuk, hogy hat kísérlet általában nem elegendő, a feladatot megoldottuk.

 
II. megoldás. Noha a feladat szerint ,,az elemek összekeveredtek'', természetes föltevés, hogy a kísérletezés során valamilyen módon azonosítani tudjuk őket. Ez azt jelenti, hogy a kísérlet bármely szakaszában bármely két elemről tudjuk, hogy kipróbáltuk-e már őket együtt és ez a kísérlet milyen eredménnyel járt. Ez például megvalósítható, ha megszámozzuk az elemeket 1-től 8-ig, mielőtt próbálkozni kezdenénk.
A 8 elemet (82)=28-féleképpen próbálhatjuk ki és ezek közül mindössze (42)=6 esetben működik a rádiónk. Első pillanatra nem látszik jobb megoldás, mint az egyes párok szisztematikus végigpróbálgatása, ez pedig a legrosszabb esetben akár 28-6=22 sikertelen kísérletet is jelenthet. Ezen a módon viszont figyelmen kívül hagyjuk a sikertelen kísérletekből leszűrhető információt. Pedig ha elemek egy csoportjában nem találunk üzemképes párt, akkor a csoportban legfeljebb egy elem lehet jó; ilyenkor jobban járunk, ha a megmaradt elemek között próbálkozunk tovább.
Ha például három elemet mindhárom csoportosításban megpróbálva egyik esetben sem szólal meg a rádió, akkor e háromból legfeljebb egy elem lehet jó. Így pedig a megmaradó öt elem között legalább három friss van és ilyenkor legfeljebb (52)-(32)=7 újabb próbálkozással után már biztosan a kezünkben lesz egy jó pár. De gyorsabban is célhoz érhetünk: a fentiekből lényegében az derült ki, hogy párok helyett ‐ egy kísérlet ‐ elemekből álló hármas csoportokat tesztelve ‐ ez három kísérletet jelent ‐ vagy találunk működő párost, vagy pedig legalább két hibás van a három elem között. Ez azt jelenti, hogy ha két hármas csoport egyikében sem találunk működő párt ‐ ez hat kísérlet ‐, akkor hármasonként legfeljebb egy-egy jó van az elemek között és így az utoljára maradt két elem már biztosan jó. Hat ilyen kísérlet után a hetedikre biztosan szól majd a rádió.
Megmutatjuk, hogy ennél kevesebb kísérlet általában nem elegendő, tehát bárhogyan is végezzünk el hat kísérletet, előfordulhat, hogy a rádió egyik alkalommal sem szólal meg. Ehhez azt bizonyítjuk be, hogy hat kísérlet után mindig lesz négy olyan elem, amelyek közül egyetlen párt sem próbáltunk még ki. Ha pedig ez a helyzet és történetesen éppen ezek az új elemek, akkor a rádió mind a hat próbálkozásra néma marad.
A bizonyításhoz készítsünk egy 8-csúcsú gráfot, amelynek csúcsai az egyes elemek, kezdetben bármely két csúcsát él köti össze és két csúcs közti élt töröljünk ki, ha a végpontjaiknak megfelelő két elemet együtt kipróbáltuk. A megmaradt gráfban tehát két csúcsot pontosan akkor köt össze él, ha a megfelelő két elemet együtt még nem próbáltuk ki. A 8-csúcsú teljes gráf (82)=28 éle közül tehát feltevésünk szerint hatot töröltünk ki, és azt kell bebizonyítanunk, hogy a kapott 8-csúcsú, 22 élű gráfnak van négy csúcsa, hogy közülük bármely kettőt él köt össze, a gráf tartalmaz ún. teljes négyszöget. Ez így ahogy van, egy úttörő magyar gráfelméleti eredmény, a Turán-tétel speciális esete1.
Az eredeti tétel bizonyítása teljes indukcióval történik, most bizonyos értelemben ennek a gondolatmenetnek a megfordításával okoskodunk: az adott gráfból kiindulva annak mind kisebb részgráfjaiban keresünk mind kisebb méretű teljes részgráfot. Eközben lényegében csak a skatulya elvet használjuk, abban a formában, hogy ha egy gráfnak ,,elég sok'' éle van, akkor csúcsai között van ,,megfelelően nagy'' fokszámú. Ez pontosabban fogalmazva azt jelenti, hogy ha egy n-csúcsú egyszerű gráfnak legalább k éle van, akkor van olyan csúcsa, amelyből legalább 2kn él indul ki. Egyszerű gráfban ugyanis az élek számának a kétszerese a csúcsok fokszámának az összege, és így a felső egészrész zárójelen belül a fokszámok átlaga áll.
Ebből most az adódik, hogy kiinduló G0 gráfunkban van olyan csúcs, amelynek a fokszáma legalább 2228=6. Legyen ez a csúcs A0, a további csúcsok közül pedig jelöljük B0-lal azt, amelyik vagy nincs összekötve A0-lal, vagy ha ilyen csúcs nincsen ‐ ekkor persze A0 hetedfokú ‐, akkor a további csúcsok közül a minimális fokszámú. Az utóbbi esetben hagyjuk is el a gráfból az A0B0 élt. Az így kapott G0' gráfban az A0 csúcsból pontosan 6 él indul ki, az első esetben legfeljebb hatodfokú B0-ból legfeljebb 6, a másodikban legfeljebb 4; ezért az A0 csúcs hat darab G0'-beli szomszédja között mindenképpen legalább 10 él halad. Jelölje G1 a G0'-nek azt a 6-csúcsú részgráfját, amelynek az A0 csúcs szomszédai a csúcsai. Világos a cél: azt kell megmutatnunk, hogy G1 tartalmaz háromszöget, teljes háromcsúcsú részgráfot; mivel G1 valamennyi csúcsát él köti össze A0-lal G0-ban, a háromszöget A0-lal kiegészítve valóban teljes négyest kapunk.
A folytatás teljesen hasonló. G1-ben van legalább 2106=4-edfokú csúcs, legyen ez A1. Az előző módszerrel válasszuk ki a B1 csúcsot és hagyjuk el az esetleges A1B1 élt. A kapott G1' gráfban az A1 pontosan negyedfokú, a szomszédai legyenek a G2 részgráf csúcsai. Az előző becslés most azt adja, hogy ha G1'-nek tíz éle van, akkor legfeljebb 9, ha pedig kilenc, akkor legfeljebb 7 él haladhat G2-n kívül; mindenképpen vannak tehát olyan G2-beli csúcsok, mondjuk A2 és A3, amelyeket él köt össze.
Az így kapott A0, A1, A2 és A3 csúcsok közül tehát valóban bármely kettőt él köt össze. Ezzel igazoltuk, hogy hat próbálkozás nem feltétlenül elegendő egy működő elempáros kiválasztására, a bizonyítást befejeztük.
 

Megjegyzések. 1. A dolgozatok általában nem a fenti gráfban, hanem annak ún. komplementerében okoskodtak. Az természetesebben illeszkedik a feladat körülményeihez: két csúcsot akkor köt össze él, ha a megfelelő elemeket együtt kipróbáltuk; a bizonyítandó állítás azonban nehézkesebb: teljes négyes helyett üres négyes meglétét kell igazolni, tehát olyan pontnégyesét, amelynek semelyik két csúcsa között nem halad él.
2. Hubai Tamás (Budapest, Fazekas Mihály Gimnázium, 12. évf.) dolgozatában általánosan oldotta meg a feladatot. A Turán-tétel fenti speciális esetének egy kiterjesztésével igazolta, hogy ha n darab jó és n darab kimerült elemünk van (n2), akkor a legrosszabb esetben n+3 próbálkozásra van szükség a rádió megszólaltatásához, ennyi viszont mindig elegendő.
1Turán Pál (1910‐1976) a számelmélet nemzetközi rangú tudósa gráfelméleti tétele, az ún. extremális gráfelmélet egyik legelső klasszikus problémája. Turán azt a kérdést vizsgálta és oldotta meg a negyvenes évek elején, hogy egy n-csúcsú gráfban hány él biztosítja teljes k-csúcsú részgráf meglétét. A feladat ennek nyilván speciális esete, ha n=8 és k=4. A témáról olvashatunk többek között Lovász László: Kombinatorikai Problémák és Feladatok (Typotex Kiadó, Budapest, 1999), illetve Hajnal Péter: Gráfelmélet (Polygon, Szeged, 1997) című könyveiben. A Typotex Kiadó most megjelent könyvében (Martin Aigner, Günter M. Ziegler: Bizonyítások a KÖNYVből) pedig nem kevesebb, mint öt bizonyítást olvashatunk az általános tételre.