Az A. 800. feladat (2021. május)

A. 800. Egy véges, egyszerű, összefüggő \(\displaystyle G\) gráf mindegyik csúcsát különböző színűre színezzük, és a következő játékot játsszuk. Egy lépés során véletlenszerűen, egyenletes eloszlással kiválasztunk egy csúcsot, majd véletlenszerűen, egyenletes eloszlással kiválasztjuk annak az egyik szomszédját, és átszínezzük olyanra, mint az eredetileg választott csúcs (ha már eleve egyszínűek, nem csinálunk semmit). A játék akkor ér véget, ha az összes csúcs színe egyforma.

Állapítsuk meg a \(\displaystyle G\) gráf ismeretében minden egyes csúcsra, hogy mekkora valószínűséggel ér véget a játék úgy, hogy az összes csúcs olyan színű, mint az adott csúcs.

Javasolta: Matolcsi Dávid (Budapest)

(7 pont)

A beküldési határidő 2021. június 10-én LEJÁRT.

Először is könnyű látni, hogy 1 valószínűséggel idővel az egész gráf egyszínű lesz.

Minden évben tekinthetem úgy, mintha az elejéről indulna a színezés, és egy csúcs esélye a világuralomra az az összege annak, hogy az ilyen színű csúcsoknak mekkora volt a folyanat kezdetén a valószínűsége, hogy végül az egész gráf ilyen színű lesz.

Nézzük a folyamat kezdetét. Legyen egy \(\displaystyle A\) csúcs színe \(\displaystyle v(A)\) valószínűséggel a végső szín.

Egy csúcs \(\displaystyle 1/n\) valószínűséggel lesz kiválasztva, ekkor ha fokszáma \(\displaystyle d\), akkor \(\displaystyle 1/d\) valószínűséggel színez át minden szomszédos \(\displaystyle A_i\) csúcsot.

A szomszédos \(\displaystyle A_i\) csúcsok is mind \(\displaystyle 1/n\) eséllyel lesznek kiválasztva, és ezután \(\displaystyle q/d_i\) eséllyel színezik át őt.

Ebből azt kapjuk, hogy \(\displaystyle v(A)=v(A)+1/n*1/d*(\sum v(A_i))-1/n*(\sum 1/d_i)*v(A)\), ahol a szummák az \(\displaystyle A\)-val szomszédos \(\displaystyle A_i\) csúcsokon futnak végig.

Vagyis \(\displaystyle (\sum 1/d_i)*v(A)-1/d*(\sum v(A_i))=0\) minden \(\displaystyle A\) csúcsra teljesül.

Könnyű látni, hogy tetszőleges \(\displaystyle \lambda\) érték esetén \(\displaystyle v(A)=\lambda/d\) kielégíti az egyenletrendszert. Mivel a valószínűségek összege 1 kell, hogy legyen, \(\displaystyle \lambda=1/(\sum 1/d)\), azaz a megoldás \(\displaystyle v(A)=1/d/(\sum 1/d)\).

Belátjuk még, hogy más vektor nem elégíti ki az egyenletrendszert.

Ha ugyanis az egyenletrendszernek megoldása lenne a \(\displaystyle w(A_i)\) vektor is, amely nem a fenti alakú, akkor a pozitív \(\displaystyle w(A_i)\) értékek közül kiválasztom azt az \(\displaystyle A_r\)-t, amelyre \(\displaystyle w(A_r)/(1/d_r)\) maximális. Legyen ez az érték \(\displaystyle \mu\), és vegyük a \(\displaystyle \mu/d_i-w(A_i)\) vektort.

Az így lineáris kombinációként kapott vektor is kielégíti az egyenletrendszert, minden koordintája nemnegatív, és az r-hez tartozó koordintája 0, viszont nem maga a \(\displaystyle \mathbf{0}\) vektor, mert \(\displaystyle w\) nem a fenti alakú.

Ilyen vektor azonban nem létezik, mert ahhoz, hogy \(\displaystyle A_r\)-nél 0 legyen és a feltételeknek eleget tegyen, az összes szomszédos csúcsnál is 0-nak kell lennie (mert a koordináták nemnegatívak), és így tovább, mivel a gráf összefüggő, minden csúcson 0-nak kell állnia.

Ezzel ellentmondásra jutottunk, tehát csak a fenti alakú megoldásai vannak az egyenletrendszernek, vagyis a korábban meghatározott valószínűség az egyetlen megoldás.

Statisztika:

2 dolgozat érkezett.
7 pontot kapott:	Fleiner Zsigmond.
4 pontot kapott:	1 versenyző.

A KöMaL 2021. májusi matematika feladatai