Feladat: N.106 Korcsoport: 18- Nehézségi fok: nehéz
Füzet: 1996/május, 298. oldal  PDF  |  MathML 
Témakör(ök): Gráfok összefüggősége, Valószínűségszámítás - Statisztika, Nehéz feladat
Hivatkozás(ok):Feladatok megoldásai: 1997/január: N.106

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.

Egy izolált (nulla fokú) pont nélküli 1996 csúcsú gráfban véletlenszerűen jelöljük ki a csúcsoknak egy részhalmazát. Mutassuk meg, hogy így 51%-nál kisebb eséllyel kapunk lefogó pontrendszert, azaz 49%-nál nagyobb valószínűséggel lesz olyan éle a gráfnak, amelynek végpontjai a kijelölt csúcsok között nem szerepelnek.