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ť:
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
(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í.
(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ť.
(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 nanie
.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.
(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 inaknie
. Môžete pridať najviac troch nových používateľov.(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.
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.
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.
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.
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\):
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ť.