Egy társaságban néhányan korábbról már ismerik egymást. Folytatás lent?

első: annyira azért nem nyilvánvaló, lehetne, hogy Csilla második partiján már megismerkedhetnének egymást (mindketten ismerik már Csillát, ezért mindketten meg annak híva), de Csilla első partijának idején Anna még nem ismerte Csillát, ezért még nem volt ott a partin.

---

Kérdező:

- ha tanultál gráfelméletet, akkor itt igaziból annyi történik, hogy ha már mindenki tartott egy partit, akkor a kiinduló gráf tranzitív lezártját kapjuk, tehát Anna és Béla pontosan akkor nem lesznek ismerősök, ha különböző összefüggőségi komonensben voltak, ekkor meg világos, hogy soha nem ismerhetik meg egymást.

- ha nem tanultál még gráfelméletet, akkor a fenti gondolat gráfelméleti fogalmak nélkül elmondva:

2 eset van: vagy létezik egy olyan "út", amin keresztül Anna megismerhetné Bélát (pl. Anna ismeri Csillát, aki ismeri Dalmát, aki ismeri Erikát, aki ismeri Bélát), vagy nincs.

Tegyük fel először, hogy van ilyen "út", a példánál maradva legyen ez az "út" az Anna-Csilla-Dalma-Erika-Béla út. Ez az út 5 emberből áll jelenleg. Ha a közbenső emberek (Csilla, Dalma, Erika) bármelyik tart egy partit (pl. most legyen ez Dalma), akkor azt az embert ki lehet venni az "útból", és lesz egy eggyel rövidebb "út" is Anna és Béla között: Anna-Csilla-Erika-Béla.

Tehát ha az összes közbenső ember tartott már partit, akkor az Anna és Béla között vezető "út" már csak emberből fog állni, tehát Anna és Béla ekkor már ismeri egymást. Szóval ha volt ilyen "út", akkor tényleg elég mindenkinek csak egyszer partit tartania, hogy a végén biztosan megismerjék egymást.

Ha viszont eleve nem volt ilyen "út" Anna és Béla között, akkor azt kell észrevenni, hogy egy partin csak olyanok ismerik meg egymást, akik között eleve volt ilyen "út". Ebből következik, hogy ha két ember között eleve nem volt út, akkor később sem lesz, függetlenül attól, hogy hány partit tartanak az emberek.