5. Komplikovanejšie Memetické Siete

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ť.

Toto je pokračovanie úlohy z minulého kola. Pri riešenení tejto úlohy môžete využívať napr. vzorové riešenie tejto úlohy.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Viktorovi 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

6. (20 bodov) Vieme, že niektoré siete sa nikdy neustália. Ale ako veľmi vieme mať kontrolu nad tým, ako sa takéto siete menia? Skúste spraviť takú sieť, že nejaký používateľ \(A\) v nej má názor ‘áno’ každý tretí krok. Inokedy má názor ‘nie’.

7. (20 bodov) Vedeli by sme postup v predošlej podúlohe spraviť všeobecnejšie? Predstavte si, že máte postupnosť názorov ‘áno’ a ‘nie’ ľubovoľnej dĺžky. Ako by vyzerala sieť, kde nejaký používateľ \(A\) mení názor každý krok podľa tejto postupnosti? Teda postupne ňou prechádza, a až príde na koniec, vráti sa na jej začiatok. Napríklad riešenie predošlej úlohy by bolo popísané postupnosťou ‘nie nie áno’.

8. (30 bodov) Skúsme spraviť ešte jednu podobnú sieť. Tentokrát požadujeme, aby používateľ ‘A’ mal názor ‘áno’ každý tridsiaty krok, a inak ‘nie’. Ľahké, však? Má to však háčik… Táto sieť môže mať iba 12 používateľov. Ako ju skonštruovať?

9. (30 bodov) Lea by chcela spraviť ešte jednu poslednú sieť. Sú v nej používatelia \(A\) a \(B\). Chcela by, aby používateľ \(B\) vždy zmenil názor na opačný, než má používateľ \(A\). Nemusí sa zmeniť hneď, stačí, aby sa po zmene používateľa \(A\) vždy sieť ustálila do takého stavu, že \(B\) je opačný. Ako by mohla takáto sieť vyzerať? Môže vôbec existovať? Ak nie, prečo?