Meddig mászkálnak a hangyák?
290. feladványunkban azt kérdeztük, hogy az alábbi négy szabályos test közül melyiknél a legkisebb a valószínűsége annak, hogy a szemközti csúcsokból induló hangyák legfeljebb tíz lépés után egy csúcsban találkoznak, ha minden lépésben véletlenszerűen és szimultán átlépnek egy szomszédos csúcsra. Az érdekesség az volt Boros Péter feladatában, hogy nem kellett hozzá semmit számolni, mert az egyik test esetében be lehetett látni, hogy soha nem találkozhatnak a hangyák, tehát a valószínűség nulla, míg a többi esetben a találkozás lehetséges. Most a legegyszerűbb esetet nézzük, amikor valóban találkozhatnak a hangyák, a kérdés viszont picit más lesz.
291. feladvány: Hangyák oktaéderen
Egy oktaéderen két hangya mászkál. Kezdetben az oktaéder két átellenes csúcsáról indulnak. Egy időlépésben mindkét hangya választ véletlenszerűen, egyenletes valószínűséggel, egy saját maga alatt lévő csúcsból kiinduló élt, és azon átmegy egy szomszédos csúcsra. Ha egy ilyen szimultán lépés után a két hangya ugyanazon a csúcson tartózkodik, akkor ott megállnak. Ha menet közben találkoznak egy él közepén, az nem számít, akkor elhaladnak egymás mellett. Átlagosan hány lépés múlva találkoznak?
Tipp
Figyelembe véve az oktaéder szimmetrikus voltát, hányféle állapotban, pozícióban lehet egymáshoz képest a hangya pár?
Megoldás
Valójában nem számít az, hogy a hangyák éppen hol vannak, csak az, hogy egymáshoz képest milyen pozícióban. Az oktaéderen csak három lehetőség van: vagy átellenesen helyezkednek el (A), vagy egymással szomszédos csúcsokon tartózkodnak (B), vagy egy helyen vannak, és akkor vége a folyamatnak (C). Kezdetben az A állapotból indulnak, és az a kérdés, hogy várható értékben hány lépés múlva kerülnek a C állapotba. Nézzük meg, hogy az A és a B állapotokból, amikből lehetséges a továbbmenetel, mekkora valószínűséggel milyen állapotba kerülnek!
Az A állapotból, mondjuk az ábra szerinti oktaéder tetejéről és aljáról, a következő lépésben mindenképpen az oktaéder vízszintesen felező négyzet egy-egy csúcsába jutnak a hangyák. Tegyük fel, hogy az egyik hangya picit előbb lép, akkor hozzá képest a másik 1/4 valószínűséggel lép ugyanoda (C), 1/2 valószínűséggel a két szomszéd csúcs közül az egyikre (B), és 1/4 valószínűséggel az átellenes csúcsba (A).
Ha a hangyák a B állapotban vannak, akkor mindkettő léphet négyfelé, összesen pedig 16 féle kombinációban léphetnek. Ha ezt a 16 lehetőséget végignézzük, akkor azt találjuk, hogy ezekből csak két eset az, amikor ugyanoda lépnek (C), mégpedig valamelyik közös háromszöglap harmadik csúcsába, és szintén két esetben lépnek átellenes csúcsokra (A), amikor szintén a közös háromszöglapok harmadik csúcsába lépnek, de nem ugyanoda, hanem az egyik az egyikre, a másik a másikra. A maradék 12 esetben szomszédos csúcsokra lépnek, tehát 1/8 eséllyel váltanak A vagy C állapotba, és 3/4 eséllyel B állapotba.
Mármost nézzük a várható lépésszámot. Mi az A állapotból keressük a várható lépésszámot, ezt nevezzük NA-nak, de nevezzük el a B állapotból várható lépésszámot is, mégpedig NB-nek. Mármost a kiszámolt átmeneti valószínűségek szerint felírhatjuk, hogy az A állapotra vonatkozóan:
NA = 1 + (1/2)·NB + (1/4)·NA,
ahol az 1 azért áll ott, mert az A állapotból 1-et mindenképpen lépnünk kell még, a többi tag pedig leírja az első lépés után még hátralévő várható lépésszámot. Ugyanilyen összefüggést felírhatunk a B állapotra is:
NB = 1 + (3/4)·NB + (1/8)·NA.
Ezt a két egyenletet megoldva az adódik, hogy NA = 6, és NB = 7, amit a kedves olvasó is könnyen ellenőrizhet. A válasz tehát az, hogy várhatóan, vagy átlagosan 6 időlépés múlva kerülnek egy csúcsba a hangyák.
Ha szereted a fejtörőket, tekintsd meg korábbi feladványainkat is! Ha megjegyzésed lenne, vagy feladványt javasolnál, írj az eszventura@qubit.hu e-mail címre! Ha pedig tetszik a rovat, ezt a Vendégkönyvben kifejezésre juttathatod.
