8. KMSáci Margecany Spratávajú vzorové riešenie

V úlohe chceme ukázať, na koľko meraní vlakvedúci vie zistiť obsahy jednotlivých množín. Takže nás čakajú \(2\) časti. Najprv ukážeme, že na \(100\) meraní už vlakvedúci vie vedieť obsahy všetkých množín. Následne ukážeme že \(100\) meraní naozaj potrebujeme.

Zatiaľ uvažujme \(3\) množiny \(A,B,C\). Spravme medzi nimi všetky merania. Najprv rýchle uvedomenie, že ak viem obsah množiny \(X\) a \(Y\), tak už mám aj obsah \(X\backslash Y\) (\(X\) bez \(Y\)). Nech \(Z = A \cup B \cup C = (A\cup B)\cup(A\cup C)\), takže \(Z\), zjednotenie všetkých \(3\) množín máme. Ďalej nech \(D = A \cap B\) a \(E = A \cap C\). Potom \(A = (Z\backslash(B \cup C)) \cup D \cup E\). Tým dostávame vyjadrenie pre \(A\) využívajúce len prieniky a zjednotenia týchto \(3\) množín. V prípade, že by to čitateľ mal problém nahliadnuť, odporúčame si nakresliť Vennov diagram. Keďže je situácia symetrická, tak vieme dorátať aj obsahy množín \(B\) a \(C\). Pre ostatných \(97\) množín postupujme nasledovne: porovnajme ich vždy po jednej (nazvime ju \(M_i\)) s množinou \(A\), ktorej obsah už je známy. Potom \(M_i = ((A \cup M_i)\backslash A) \cup (A\cap M_i)\) nám dáva postupne obsahy ostávajúcich množín. Dokopy to sú \(3\) merania na odhalenie množín \(A,B,C\) a potom \(97\) ďalších meraní, čím sme zakončili prvú časť dôkazu.

Náročnejšou pasážou je ukázať, že \(100\) meraní naozaj potrebujeme. Respektíve vyžaduje nie úplne očividný nápad, že množiny si vieme reprezentovať ako vrcholy grafu a merania ako hrany medzi nimi. Najprv predpokladajme, že sme spravili najviac \(99\) meraní. Potom náš graf má aspoň jeden komponent súvislosti neobsahujúci cyklus. To nahliadneme z toho, že súvislý graf na \(n\) vrcholoch musí mať aspoň \(n-1\) hrán a potrebuje ich aspoň \(n\) aby obsahoval cyklus. Ak každý vrchol je v komponente súvislosti s cyklom, tak každý komponent má aspoň toľko hrán ako vrcholov. Takže náš graf by musel mať aspoň \(100\) hrán, čo nemá podľa predpokladu. Ak má tento acyklický komponent jeden vrchol, tak sme sa na danú množinu nepýtali, a teda nemôžeme poznať jej obsah. Ak je komponent aspoň \(2\)-vrcholový, tak ide o strom, špeciálne je bipartitný (vieme ho rozdeliť na \(2\) množiny, kde v rámci každej nevedú hrany), kde obe partície sú neprázdne. Predstavme si, že by jedna partícia obsahovala iba prázdne množiny a druhá množiny obsahujúce prvok \(a\). Potom \(a\) leží v každom zjednotení (na aspoň jednom konci každej hrany) a v žiadnom prieniku (nikdy nie na oboch). Potom však nevieme určiť, v ktorej z týchto \(2\) partícií sa \(a\) nachádza a ktorá je prázdna, takže \(99\) meraní nestačí.

Pozorný čitateľ v tomto momente môže namietať, že prvok \(a\) sme do množín umiestnili až po tom, čo prebehli porovnania, pričom normálne proces prebieha obrátene. Naša stratégia však vie teoreticky záležať na obsahu daných množín, a teda ho nevieme umiestniť BUNV na konci. Táto námietka je oprávnená, no nevadí nám. Ukážeme, že hneď na začiatku vieme do množín zadeliť prvky tak, aby nech počas konštrukcie vznikne akýkoľvek strom, tak daný prvok bude mať v každom druhom vrchole. Spravíme to priamočiaro. Stromov, ktoré mohli vzniknúť, je na \(100\) vrcholoch iba konečne veľa. Postupne ich prejdime a každému dajme na každé druhé miesto prvok. Potom, keď pri konštrukcii vznikne akýkoľvek strom, ako komponent súvislosti, tak sa v ňom nachádza prvok, ktorý bude ležať v každom zjednotení a žiadnom prieniku, a teda nebudeme vedieť, v ktorej partícií sa bude nachádzať, čím je náš dôkaz naozaj ukončený.