5. Komunikácia mojich svetonázorov

Táto úloha je teoretická. Ako svoje riešenie odovzdaj pdf súbor, v ktorom bude tvoje riešenie aj so zdôvodnením, prečo je správne. Po konci kola ti riešenie opraví vedúci, a napíše ti komentár - povie ti kde si spravil chyby, prípadne ti poradí ako vieš svoje riešenia zlepšiť.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Štepimu na [email protected]

Lea sleduje rôzne sociálne siete a zaujíma sa tam o najnovšie trendy. To však nie je len tak, lebo keď niečo zazdieľa veľká skupina ľudí, môžu o tom presvedčiť aj ďalších, ktorí to pošlú zase ďalej. Zdanlivo nenápadné posty potom môžu spôsobiť veľké a dôležité zmeny, ako napríklad vo výsledkoch volieb. Lenže to, ako ľudia na sociálnych sieťach menia svoje názory, môže byť veľmi komplikované a ťažké odsledovať, a kto sa v tom má vyznať?

Lea sa rozhodla, že si v tom skúsi urobiť aspoň trochu poriadok, a preskúma, ako sa takéto siete môžu správať.

Siete

Sociálna sieť má niekoľko používateľov. Každý z nich má nejaký názor, buď áno alebo nie, podľa toho, či s niečím súhlasia alebo nie. Okrem toho môže každý používateľ sledovať niekoľkých ďalších. Každý použivateľ zmení svoj názor práve vtedy, keď má opačný názor viac ako polovica používateľov, ktorých sleduje. Všetci, ktorí majú zmeniť svoj názor, to urobia vždy naraz.

Ukážme si to na príklade. Používateľov si môžeme nakresliť ako krúžky, ktoré vyfarbíme, ak ten používateľ má názor áno. Okrem toho, ak používateľ niekoho sleduje, nakreslíme k nemu šípku od toho, koho sleduje.

Predstavme si takúto sieť:

Najprv používatelia \(D\) a \(E\) presvedčia \(C\), zatiaľčo názor \(A\) ostáva nezmenený. Až potom \(B\) aj \(C\) presvedčia \(A\). Teraz už majú všetci rovnaký názor, takže sa nič nebude ďalej meniť.

Úlohy

1. (10 bodov) Pri skúmaní rôznych sietí si Lea všimla, že niekedy sa sieť dostane do takého stavu, že nikto už ďalej nemení svoj názor. Nájdite aj vy takú sieť, kde nemajú všetci rovnaký názor, ale napriek tomu nikto svoj názor nezmení.

2. (10 bodov) Veľa sietí sa zo začiatku mení, ale nakoniec sa dostanú do stavu, kedy sa už ďalej nemenia. Musí to tak ale byť vždy? Nájdite takú sieť, ktorá sa nikdy neprestane meniť.

3. (20 bodov) Lea objavila aj nejaké špeciálne siete, ktoré mali rôzne zaujímavé vlastnosti. Napríklad si predstavme sieť s používateľmi \(A\), \(B\), \(C\). Táto sieť mala tú vlastnosť, že \(A\) vždy zmenilo názor na áno vtedy, ak \(B\) aj \(C\) mali názor áno, a inak na nie.

   Nájdite aj vy sieť, ktorá bude takto fungovať. Názory \(B\) a \(C\) sa môžu ľubovoľne meniť. Ostatným môžete určiť, koho majú sledovať a aký názor majú mať na začiatku. Navyše môžete pridať najviac jedného nového používateľa, ktorému takisto určíte tieto veci.

4. (30 bodov) Čo ak máme viacerých používateľov? Máme používateľov \(A\) a \(B_1, B_2, B_3, B_4\). Podobne ako pri úlohe (c.) nájdite sieť, kde \(A\) bude mať názor áno, keď všetci \(B_1\) až \(B_4\) majú tiež názor áno, a inak nie. Môžete pridať najviac troch nových používateľov.

5. (30 bodov) Niekedy na zmenu názoru treba viac ako polovicu z nejakej skupiny používateľov. Máme používateľov \(A\) a \(B_1, B_2, \dots, B_5\). Nájdite takú sieť, kde \(A\) zmení názor, ak aspoň štyria z \(B_1\) až \(B_5\) majú opačný názor, a inak si nechá svoj aktuálny názor. Môžete pridať najviac štyroch nových používateľov.