Boros Péter olvasónk küldte be az alábbi feladatot.

290. feladvány: Két hangya találkozása

Adott négy szabályos test, egy oktaéder, egy kocka, egy dodekaéder és egy ikozaéder. Mindegyiken található két hangya, és kiinduláskor minden testen átellenes csúcsokban vannak a hangyák. Egy lépésben minden hangya választ véletlenszerűen, egyenletes valószínűséggel, egy saját maga alatt lévő csúcsból kiinduló élet, és azon elmegy a következő csúcsig. Ha egy ilyen szimultán lépés után a két hangya ugyanabban a csúcsban van, ott megállnak.

Melyik test esetén legkisebb a valószínűsége annak, hogy a hangyák legfeljebb tíz lépés után egy csúcsban találkoznak? Ha menet közben találkoznak egy él közepén, az nem számít.

Tipp

Az egyik test esetében ez a valószínűség nulla. Vajon melyik lehet az?

Megoldás

A kocka éleinek hálózata egy páros gráf. Ez azt jelenti, hogy a csúcsok két osztályba sorolhatók, például két színnel színezhetők úgy, hogy minden él az egyik osztályból a másikba megy, vagyis azonos színű csúcsok között nem megy él, lásd az ábrát.

Mármost a kocka két átellenes csúcsa különböző színű, a hangyák pedig minden lépésben színt váltanak a lépésükkel, azaz átmennek egy másik színű csúcsra, ezért minden lépés után továbbra is eltérő színű csúcsokon lesznek, így soha nem lehetnek egyszerre ugyanazon a csúcson. Tehát nulla a valószínűsége annak, hogy egy csúcson találkozzanak.

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.