Zadanie

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

príklad siete

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.

Podúloha A

Predstavme si sieť s tromi používateľmi \(A, B, C\), kde \(A\) sleduje \(B\) aj \(C\) a \(B\) ani \(C\) nesledujú nikoho. Názor \(B\) a \(C\) sa potom nikdy nemení. Ak majú navyše \(B\) a \(C\) rôzne názory, tak názor \(A\) sa tiež nikdy nebude meniť, lebo na zmenu by bolo treba, aby viac ako polovica ľudí, ktorých sleduje, mala rovnaký názor,

čiže by museli mať \(B\) aj \(C\) rovnaký názor.

príklad siete

Podúloha B

Funguje sieť s troma používateľmi \(A, B, C\), kde \(A\) sleduje \(B\), \(B\) sleduje \(C\), a \(C\) zase \(A\). Dajme tomu, že \(A\) má na začiatku názor áno a \(B\) a \(C\) nie. Keďže každý sleduje len jedného, tak po ňom vždy preberá názor. Názory sa teda v každom kroku posunú do kruhu.

príklad siete

Podúloha C

\(A\) zmení názor vtedy, keď zmení názor polovica ľudí, ktorých sleduje. To znamená, že keď \(B\) aj \(C\) majú názor áno, musí mať viac ako polovica z ľudí, ktorých sleduje \(A\), názor áno; ale inak to musí byť menej ako polovica.

Môžeme teda spraviť to, že \(A\) bude sledovať \(B\) aj \(C\), ale ešte navyše aj ďalšieho človeka \(D\), ktorý bude mať celý čas názor nie.

Môžete si rozmyslieť, že táto sieť naozaj funguje tak, ako chceme.

príklad siete

Podúloha D

Teraz sa snažíme spraviť to isté, ale s viacerými používateľmi. Chceme teda, aby všetci \(B_1, \dots, B_4\) tvorili viac ako polovicu tých, čo sledujú \(A\), ale nejaká menšia skupina z nich už tvorila menej ako polovicu.

Nech teda \(A\) sleduje všetkých \(B_1, \dots, B_4\) a ešte troch ďalších, ktorí majú stále názor nie. Takto dostaneme sieť, ktorú chceme.

príklad siete

Podúloha E

Doteraz sme pridávali používateľov, ktorí mali stále rovnaký názor. Tým sme dosiahli, že treba viac ľudí na presvedčenie \(A\) na áno, ale menej ľudí na presvedčenie \(A\) opačným smerom. Teraz chceme, aby bolo treba viac ľudí na presvedčenie oboma smermi.

Keď má teda \(A\) názor nie, chceme, aby sledovalo ešte navyše nejakých používateľov s názorom nie, a keď má názor áno, chceme, aby sledovalo navyše používateľov s názorom áno.

Ako toto docielime? Chceli by sme pridať používateľa, ktorý bude mať rovnaký názor ako \(A\). Stačí teda pridať používateľa, ktorý bude sledovať \(A\).

Tým dostávame takúto sieť, kde nový používateľ začína s rovnakým názorom ako \(A\):

príklad siete

Teraz ak práve traja používatelia (z $B_1 až \(B_5\)) majú opačný názor ako \(A\), tak zvyšní dvaja plus ten pridaný majú rovnaký názor, takže stav siete sa nezmení. Ak viac ako traja používatelia súhlasia s \(A\), potom to už stačí na to, aby ho presvedčili, a ak menej, potom aspoň traja majú opačný názor. Podobne sa teda stav siete buď zachová alebo zmení opačným smerom, čo sme presne chceli dosiahnuť.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.