Kezdőlap


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 \| MathML
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

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 $6 \cdot 2 = 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 $(\binom{4}{2}) = 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

(\binom{8}{2}) = 28

-féleképpen próbálhatjuk ki és ezek közül mindössze

(\binom{4}{2}) = 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

(\binom{5}{2}) - (\binom{3}{2}) = 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

(\binom{8}{2}) = 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 esete¹.
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

⌈ \frac{2 k}{n} ⌉

é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ó

G_{0}

gráfunkban van olyan csúcs, amelynek a fokszáma legalább

⌈ \frac{2 \cdot 22}{8} ⌉ = 6

. Legyen ez a csúcs

A_{0}

, a további csúcsok közül pedig jelöljük

B_{0}

-lal azt, amelyik vagy nincs összekötve

A_{0}

-lal, vagy ha ilyen csúcs nincsen ‐ ekkor persze

A_{0}

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

A_{0} B_{0}

élt. Az így kapott

G_{0}'

gráfban az

A_{0}

csúcsból pontosan 6 él indul ki, az első esetben legfeljebb hatodfokú

B_{0}

-ból legfeljebb 6, a másodikban legfeljebb 4; ezért az

A_{0}

csúcs hat darab

G_{0}'

-beli szomszédja között mindenképpen legalább 10 él halad. Jelölje

G_{1}

G_{0}'

-nek azt a 6-csúcsú részgráfját, amelynek az

A_{0}

csúcs szomszédai a csúcsai. Világos a cél: azt kell megmutatnunk, hogy

G_{1}

tartalmaz háromszöget, teljes háromcsúcsú részgráfot; mivel

G_{1}

valamennyi csúcsát él köti össze

A_{0}

-lal

G_{0}

-ban, a háromszöget

A_{0}

-lal kiegészítve valóban teljes négyest kapunk.
A folytatás teljesen hasonló.

G_{1}

-ben van legalább

⌈ \frac{2 \cdot 10}{6} ⌉ = 4

-edfokú csúcs, legyen ez

A_{1}

. Az előző módszerrel válasszuk ki a

B_{1}

csúcsot és hagyjuk el az esetleges

A_{1} B_{1}

élt. A kapott

G_{1}'

gráfban az

A_{1}

pontosan negyedfokú, a szomszédai legyenek a

G_{2}

részgráf csúcsai. Az előző becslés most azt adja, hogy ha

G_{1}'

-nek tíz éle van, akkor legfeljebb 9, ha pedig kilenc, akkor legfeljebb 7 él haladhat

G_{2}

-n kívül; mindenképpen vannak tehát olyan

G_{2}

-beli csúcsok, mondjuk

A_{2}

és

A_{3}

, amelyeket él köt össze.
Az így kapott

A_{0}

A_{1}

A_{2}

és

A_{3}

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 (

n \geq 2

), 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ő.

¹Turá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.