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ť.
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
(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’.
(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’.
(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ť?
(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?
Podúloha F
Uvedomme si, že ak používateľ sleduje jediného používateľa, tak v každom kroku má práve taký názor, aký mal tento sledovaný používateľ v minulom. Ľahko si uvedomíme, že ak pospájame viacero používateľov do cyklu tak, že každý sleduje práve jedného prechádzajúceho, tak ich názory sa budú večne cykliť v smere sledovania. Teda ak chceme sieť, kde používateľ \(A\) má názor áno práve v každom treťom kroku, mohli by sme spojiť troch používateľov do trojuholníku a jedinému z nich dať názor áno. Tento názor akoby začne ‘cestovať’ po cykle a v každom treťom kroku bude u používateľa \(A\). Tu je nákres, ako sa takáto sieť môže v čase meniť:
Podúloha G
Riešenie minulej podúlohy môžeme aj zovšeobecniť. Namiesto trojuholníku spravíme väčší cyklus, a jeho počiatočnými stavmi spravíme žiadanú postupnosť. Takto sa táto postupnosť bude cyklom ‘točiť’ a používateľ \(A\) bude meniť názor podľa nej.
Podúloha H
Zadanie je podobné ako v predošlých podúlohách, až na to, že tentokrát je dostupný počet používateľov veľmi obmedzený. Budeme musieť vytvoriť nejakú premyslenejšiu konštrukciu, ako len cyklus pozostávajúci z tridsiatich vrcholov…
Uvedomme si, že vlastne chceme rozlíšiť každý krok, ktorého poradové číslo je násobkom \(30\). To je rovnaké, ako keby sme rozlišovali, či je poradové číslo násobkom \(5\) a \(6\) zároveň. Spravme teda dva cykly dĺžok \(5\) a \(6\). Pokiaľ výstupného používateľa napojíme na jedného používateľa z oboch cyklov, zmení sa mu názor na áno práve vtedy, keď obaja títo používatelia budú mať názor áno. Ešte sa treba uistiť, že jeho názor sa hneď potom zmení naspäť na nie. V ďalšom kroku sa výstupy oboch cyklov zmenia na nie, takže sa zmení aj výstupný používateľ na nie. Nákres:
Podúloha I
Predstavme si, že máme sieť so vstupným a výstupným používateľom. Názor vstupného používateľa nech je nie a názor výstupného áno. Momentálne sa sieť nachádza v stabilnom stave a sama od seba sa nebude meniť. Predstavme si, že zmeníme názor vstupného používateľa na áno. Uvedomme si, že to nikdy nespôsobí, že používateľ, ktorý mal na začiatku názor áno, zmení názor na nie. Dokážme to sporom, predstavme si, ako by vyzeral protipríklad: V nejakom momente po zmene vstupného používateľa sa stane, že nejaký používateľ \(Z\) s pôvodným názorom áno ho zmení na nie. Keďže pôvodne bol jeho názor stabilný, nutne to musí znamenať, že z používateľov, ktorých \(Z\) sleduje, má názor nie viac, ako malo pôvodne. To ale nutne musí znamenať, že niektorý z týchto používateľov, ktorý mal pôvodne názor áno, zmenil názor na nie. Dokonca sa tak stalo ešte pred tým, ako názor zmenil \(Z\). Teda sme ukázali, že každý používateľ s pôvodným názorom áno ho zmení na nie až potom, ako to spraví nejaký iný pred ním. Ale ktorý používateľ to spravý ako prvý? Žiaden. Teda sme dokázali, že žiaden takýto používateľ nebude. Takže výstupný používateľ, ktorý mal názor áno, nebude mať nikdy názor nie, ak iba zmeníme názor vstupného používateľa. Takže žiadanú sieť nie je možné zostrojiť.
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ť.