Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 4322. feladat (2011. január)

B. 4322. Egy állásinterjúra öt embert hívnak be, öt előre adott lehetséges időpontra. Minden jelentkező egy adatlapon megjelöl az öt időpontból kettőt. Mi a valószínűsége, hogy mindenkit meg tudnak hallgatni az egyik általa megjelölt időpontban?

Javasolta: Holló Gábor (Budapest)

(4 pont)

A beküldési határidő 2011. február 10-én LEJÁRT.


Megoldás. Ha \(\displaystyle n\ge 2\) embert szeretnének \(\displaystyle n\) előre adott lehetséges időpontra behívni úgy, hogy mindenki két lehetséges időpontot jelöl meg, akkor ennek szükséges feltétele, hogy minden \(\displaystyle k\le n\) esetén a jelentkezők közül bármely \(\displaystyle k\) ember együttesen legalább \(\displaystyle k\) időpontot megjelöljön. (Ez a feltétel egyben elégséges is, de erre a megoldás során nem lesz szükségünk). Készítsük el a következő páros gráfot. Az egyik színosztály csúcsai legyenek a jelentkezők, a másikéi az időpontok, és minden jelentkezőt kössünk össze az általa megjelölt két időponttal. Ennek a gráfnak 10 csúcsa és 10 éle van. Ha a gráf nem összefüggő, akkor a fenti feltétel szerint minden összefüggőségi komponense egy olyan páros gráf kell legyen, amelyben a két színosztály mérete ugyanakkora, az élek száma pedig megegyezik a csúcsok számával. Stratégiánk a következő lesz: először megvizsgáljuk, mely szóbajövő gráfok esetén létesíthető a színosztályok között a kívánt teljes párosítás, majd minden egyes ilyen gráfra leszámoljuk, hogy az \(\displaystyle {5\choose 2}^5=100000\) lehetőség között az adott gráf hányszor fordul elő.

Hasznos lesz a következő észrevétel. Ha egy \(\displaystyle n\) szögpontú gráf összefüggő, akkor legalább \(\displaystyle n-1\) éle van, és pontosan akkor nem tartalmaz kört, ha csak \(\displaystyle n-1\) éle van. Ebből következik, hogy ha a gráfnak \(\displaystyle n\) éle van, akkor pontosan egy kör lesz benne. Páros gráf esetén ennek a körnek a hossza páros, és található benne párosítás.

Mármost ha a választott időpontokhoz tartozó gráf nem összefüggő, akkor az egyik komponensének 4, a másiknak 6 csúcsa van. Tehát az első komponens egy 4 hosszú kör, a másik pedig vagy egy 6 hosszú kör, vagy tartalmaz egy 4 hosszú kört. Ez a kör mindkét színosztályból egy-egy csúcsot kihagy, melyeket egy él köt össze, ha a meghallgatás lehetséges. Az élnek az első színosztályba eső végpontja pedig össze van kötve a 4 hosszú kör másik színosztályba eső valamelyik csúcsával. Ezek alapján két különböző nem összefüggő gráf van, amely a feltételeket teljesíti, jelölje ezeket \(\displaystyle G_1\) és \(\displaystyle G_2\).

Ha a gráf összefüggő, akkor egy 10, egy 8, egy 6, vagy egy 4 hosszú kört tartalmaz. A 10 hosszú kör esetén meg is kaptuk az egész gráfot, ezt jelölje \(\displaystyle G_3\). Ha 8 hosszú körünk van, akkor ez mindkét színosztályból egy-egy csúcsot kihagy, melyek össze kell legyenek kötve egy éllel, hiszen a kör csúcsait egymás között kell párosítanunk, továbbá ennek az élnek az első színosztályba eső végpontja össze van kötve a 8 hosszú kör másik színosztályba eső valamelyik csúcsával. Így kapjuk a \(\displaystyle G_4\) gráfot. Ha 6 hosszú körünk van, akkor ez mindkét színosztályból két-két csúcsot hagy ki, melyek egymás között össze kell legyenek párosítva. Ebben a párosításban mindkét él első színosztályba eső végpontja össze van kötve a második színosztály valamelyik pontjával. Három esetet különböztethetünk meg, mivel legalább az egyiknek a 6 hosszú körhöz kell csatlakoznia. Ha pontosan az egyik csatlakozik a 6 hosszú körhöz, ahhor a \(\displaystyle G_5\) gráfot kapjuk, ha pedig mindkettő, akkor a \(\displaystyle G_6\), illetve a \(\displaystyle G_7\) gráfhoz jutunk aszerint, hogy a 6 hosszú körnek ugyanahhoz a csúcsához csatlakoznak, vagy sem.

Végül ha 4 hosszú körünk van, akkor mindkét színosztályból három-három pont marad ki, melyek egymás között össze kell legyenek párosítva. Mivel legalább az egyik élnek a 4 hosszú körhöz kell csatlakozni, az alábbi hat gráfot kapjuk az eddigiek mellé.

Jelölje \(\displaystyle a_i\) azon lehetőségek számát, amikor a \(\displaystyle G_i\) gráf jön létre. Ha a gráf nem összefüggő, akkor a 4 pontú komponens csúcsait bármelyik színosztályból \(\displaystyle {5\choose 2}=10\)-féleképpen választhatjuk ki, a 4 pont kiválasztása után rajtuk a 4 hosszú kör lerajzolása már egyértelmű. A \(\displaystyle G_1\) gráf esetében a fennmaradó 6 ponton a 6 hosszú kört 6-féleképpen tudjuk megrajzolni, a \(\displaystyle G_1\) gráf tehát \(\displaystyle a_1=10\times 10\times 6=600\) alkalommal jön létre. A \(\displaystyle G_2\) gráf esetében a 6-pontú komponensen a 4 hosszú kör kiválasztása \(\displaystyle {3\choose 2}^2=9\)-féleképpen történhet, az ettől diszjunkt él első színosztályba eső csúcsát ehhez kétféleképpen tudjuk csatlakoztatni. Így \(\displaystyle a_2=100\times 9\times 2=1800\). Ahhoz, hogy egy 10 hosszú kört rajzoljunk, induljunk el az első színosztály első csúcsából, ezt összeköthetjük a második színosztály bármelyik pontjával. Innen a kör 4-féleképpen folytatható, mert az első színosztályban már csak 4 csúcs maradt szabadon. Onnan megint 4-féleképpen folytathatjuk a kört a második színosztály fennmaradt pontjaival, de ezután már csak 3 lehetőség nyílik a folytatásra, és így tovább, a hetedik él behúzása után viszont már a befejezés egyértelmű lesz. Ez tehát \(\displaystyle 5\times 4\times 4\times 3\times 3\times 2\times 2=5\cdot(4!)^2=2880\) lehetőség. Viszont így mindegyik kört kétszer számoltuk, vagyis \(\displaystyle a_3=2880/2=1440\). A \(\displaystyle G_4\) gráf esetében a 8 hosszú kör csúcsainak kiválasztására \(\displaystyle 5\times 5=25\) lehetőségünk van, a kiválasztott pontokon a kör megrajzolása \(\displaystyle 4(3!)^2/2=72\)-féleképpen történhet. Ezután a körtől diszjunkt él első színosztályba eső csúcsát ehhez négyféleképpen tudjuk csatlakoztatni, vagyis \(\displaystyle a_4=25\times 72\times 4= 7200\). A \(\displaystyle G_5,G_6,G_7\) gráfok esetében a 6 hosszú kört \(\displaystyle 10\times 10\times 6=600\)-féleképpen vehetjük fel. A kimaradó 4 pont párosítása mindegyik esetben kétféleképp történhet, ami után a gráf befejezésére rendre 6, 3, illetve 6 lehetőség adó dik. Ezek szerint \(\displaystyle a_5=a_7=600\times 2\times 6=7200\), \(\displaystyle a_6=3600\). Végül a \(\displaystyle G_8-G_{13}\) gráfok esetében a 4 hosszú kör felvétele 100-féleképpen történhet, ezután a maradék 6 pont párosítására 6 lehetőségünk van, majd a befejezés rendre 12, 6, 12, 12, 2, illetve 6 különböző módon lehetséges. Ennek alapján \(\displaystyle a_8=a_{10}=a_{11}=7200\), \(\displaystyle a_{12}=1200\) és \(\displaystyle a_9=a_{13}=3600\).

Összefoglalva, a jelentkezők időpontmegjelölésének 100000 elképzelhető kimenetele közül \(\displaystyle a_1+\ldots+a_{13}=59040\) esetben tudnak mindenkit meghallgatni az egyik általa megjelölt időpontban. A keresett valószínűség tehát \(\displaystyle 0,5904\).


Statisztika:

60 dolgozat érkezett.
4 pontot kapott:Bunth Gergely.
3 pontot kapott:Homonnay Bálint.
2 pontot kapott:7 versenyző.
1 pontot kapott:13 versenyző.
0 pontot kapott:37 versenyző.
Nem versenyszerű:1 dolgozat.

A KöMaL 2011. januári matematika feladatai