Zadanie
Vedúci Trojstenu používajú na komunikáciu tri rôzne sociálne siete: Facebook, Google Hangouts a Slack. Každá sociálna sieť funguje nasledovne. Každý vedúci má na nej niekoľko priateľov. Priateľstvá sú vzájomné. Profil každého vedúceho má nejakú farbu, nemusí byť rovnaká na všetkých sociálnych sietiach. Pre farby profilov platí, že profily vedúcich, ktorí sú priateľmi, musia mať rôznu farbu. Ďalej vieme, že na Facebooku stačí vedúcim \(42\) farieb, na Hangouts \(47\) farieb a na Slacku \(17\) farieb.
Keďže vedúci majú chaos v sociálnych sieťach, založili si vlastnú sieť – Perfektne Organizovaný Komunikačný Elektronický Chat (skrátene POKEC). Každý vedúci tam má za priateľov svojich priateľov zo všetkých troch pôvodných sietí. Na POKEC-i platia rovnaké pravidlá pre farby profilov. Dokážte, že profilom vedúcich na POKEC-i stačí \(33\, 558\) farieb, a to bez ohľadu na to, koľko je vedúcich a ako sa na jednotlivých sieťach priatelia.
Pri riešení úloh, ako je táto je dôležité uvedomiť si, že nezáleží, koľko vedúcich má rovnakú farbu na ktorej sieti, aké farby používame, ani na tom, že ich niektorí toľko ani nerozoznáme. Potrebujeme len ukázať, že pre zadaný počet farieb (v našom prípade \(33\,558\)) a dané pravidlá ich rozdeľovania určite dostaneme správny výsledok.
Začali by sme jednoduchým pozorovaním. Číslo \(33\,558\) môže vyzerať náhodne, ale ako to už býva, náhodné nie je. Platí totiž \(33\,558 = 42 \cdot 47 \cdot 17\). Tieto činitele sú počtami farieb využívaných na pôvodných sieťach.
Na základe pozorovania dostávame myšlienku, ktorá by mohla viesť naše riešenie – ak by sme každej trojici farieb pridelili jednu farbu na POKEC-i, potom by na POKEC-i bolo práve \(33\,558\) farieb. To nám však na kompletné riešenie nestačí. Nápad je to dobrý, ale ešte potrebujeme ukázať, že takéto priradenie farieb spĺňa pravidlá zo zadania.
Ak sú dvaja vedúci priatelia na POKEC-i (a teda majú na POKEC-i rôznu farbu profilu), museli byť priateľmi na niektorej z pôvodných sietí, z čoho však vyplýva, že museli mať aspoň jednu z trojice farieb rôznu. Avšak pre dve rôzne trojice pôvodných farieb máme rôznu farbu na POKEC-i, a teda pravidlá sú zachované.
Ak dvaja vedúci nie sú priateľmi na POKEC-i (a teda na ňom majú rovnakú farbu profilu), nemohli byť priateľmi ani na žiadnej z pôvodných sietí. Teda mohli mať na každej z nich priradenú rovnakú farbu. Z toho ale vyplýva, že celá trojica ich farieb bola rovnaká, a teda aj na POKEC-i budú mať podľa nášho systému rovnakú farbu profilu. Žiadne farby navyše takto nevzniknú a pravidlá sú zachované.
Keďže nás iný typ vzťahov medzi vedúcimi pri riešení tejto úlohy nezaujíma a pre všetky dôležité typy vzťahov sú pravidlá pri \(33\,558\) farbách zachované, riešenie je kompletné.
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ť.