Opravovatelia

Dominik [email protected]

Krivoš [email protected]

Nech na začiatku je na pravej strane množina drevorubačov $R$, a na ľavej $L$, kde $|L|>|R|$. Označme $C$ množinu všetkých čísel, ktoré majú drevorubači na chrbtoch. Všimnime si, že ak premiešame tým istým číslom dvakrát, nič sa nezmení. Preto nás pri každom čísle z $C$ zaujíma iba parita počtu premiešaní týmto číslom. Preto premiešanie môžeme vlastne chápať ako výber nejakej podmnožiny $P$ z $C$, pri ktorom každý drevorubač ktorý má na chrbte nepárne veľa čísel z $P$ zmení stranu, a drevorubač ktorý má na chrbte párne veľa čísel z $P$ ostane na svojej strane ($P$ sú vlastne iba všetky tie čísla z $C$ ktorými sme premiešavali nepárne veľa krát). Množiny, ktoré vzniknú z $R,L$ do premiešaní $P$ označme $R_P,L_P$. Uvažujme teraz hodnotu $$S=\sum_{P\subseteq C} (|R_P|-|L_P|)$$ (teda sumujeme cez všetky rôzne premiešania $P\subseteq C$ ako sme ich definovali vyššie). Pozrime sa na jedného konkrétneho drevorubača $d$ s číslami na chrbte $C_d$. Potom drevorubač $d$ zmení pri premiešaní $P$ stranu práve vtedy, ak sme do $P$ vybrali nepárne veľa prvkov z $C_d$. Avšak nepárnych podmnožín $C_d$ je rovnako veľa ako párnych podmnožín $C_d$,¹ a zvyšok čísel z $C\backslash C_d$ vieme do $P$ doplniť rovnako veľa spôsobmi v oboch prípadoch. Teda existuje rovnako veľa premiešaní $P\subseteq C$ takých, že $|P\cap C_d|$ je párne (teda drevorubač $d$ ostane na svojej strane), ako takých premiešaní $P\subseteq C$, že $|P\cap C_d|$ je nepárne (teda drevorubač $d$ zmení stranu). Z toho vyplýva, že v sume $S$, započítame každého drevorubača rovnako veľa krát na pravej strane (v množine $R_P$), ako na ľavej strane (v množine $L_P$). Preto dostávame $S=0$.

Všimnime si, že $|R_{\emptyset}|-|L_{\emptyset}|=|R|-|L|<0$ zo zadania. Nakoľko $S=0$ a suma $S$ v sebe má záporný sčítanec, tak to znamená, že musí mať aj kladný sčítanec, teda existuje premiešanie $P$ také, že $|R_P|-|L_P|>0$, teda $|R_P|>|L_P|$.

Iné riešenie

(pravdepodobnostná formulácia)

Zostrojme bipartitný graf s partitami $D$ a $C$. Vrcholy v $D$ budú reprezentovať drevorubačov, vrcholy v $C$ budú reprezentovať čísla. Hrana medzi vrcholmi $d \in D$ a $c \in C$ vedie práve vtedy keď drevorubač $d$ má vytetované číslo $c$ na chrbte. Každý vrchol $d \in D$ ofarbíme načierno, ak drevorubač $d$ sa nachádza naľavo a nabielo, ak sa $d$ nachádza napravo. Potom premiešanie zo zadania znamená, že si vyberieme vrchol $c \in C$ a každému jemu susednému vrcholu z $D$ zmeníme farbu. Chceme ukázať, že ak začíname s viac čiernymi vrcholmi ako s bielymi, tak vieme po konečnom počte operácií skončiť s viac bielymi vrcholmi ako čiernymi.

Lemma 1. Nech je $a$ čiernych vrcholov a $b$ bielych vrcholov, pričom $a > b$. Potom vieme spraviť operácie tak, aby sme skončili s viac ako $b$ bielymi vrcholmi.

Dôkaz. Každý vrchol z $C$ vyberieme so šancou $p = \frac{1}{2}$. Ukážeme, že každý vrchol v $D$ má šancu $\frac{1}{2}$ zmeniť svoju farbu. Zoberme si ľubovoľný vrchol $d \in D$ a nech susedí práve s vrcholmi $c_1, c_2, \dots c_k \in C$. Farbu zmení, ak je počet aktivovaných $c_i$ nepárny. Pozrime sa, aká je šanca, že aktivujeme nepárny počet vrcholov, keď postupne aktivujeme vrcholy $c_1, c_2, \dots, c_k$, každý so šancou $\frac{1}{2}$. Nech máme $l$ aktivovaných vrcholov medzi vrcholmi $c_1, c_2, \dots, c_{k-1}$. Ak je $l$ nepárne, tak je šanca $\frac{1}{2}$, že neaktivujeme vrchol $c_k$, teda že celkovo budeme mať nepárny počet aktivovaných vrcholov medzi $c_1, c_2, \dots, c_k$. Podobne ak je $l$ párne, tak je šanca $\frac{1}{2}$, že aktivujeme vrchol $c_k$, teda že budeme mať nepárny počet aktivovaných vrcholov v medzi $c_1, c_2, \dots, c_k$. Celkovo teda máme šancu $\frac{1}{2}$, že bude počet aktivovaných vrcholov medzi $c_1, c_2, \dots, c_k$ nepárny. To znamená, že pre ľubovoľné $d \in D$ je šanca, že zmení farbu $\frac{1}{2}$. Z linearity strednej hodnoty potom plynie, že stredná hodnota počtu čiernych vrcholov, ktoré zmenia farbu je $\frac{a}{2}$ a stredná hodnota počtu bielych vrcholov, ktoré zmenia farbu $\frac{b}{2}$.² Keďže $a>b$, tak $\frac{a}{2}> \frac{b}{2}$, teda v strednej hodnote sa nám zvýši počet bielych vrcholov, teda musí existovať spôsob, ako aktivovať niekoľko vrcholov z $C$ tak, aby sa počet bielych vrcholov zväčšil. $\square$

Lemma 2. Nech je $a$ čiernych a $b$ bielych vrcholov, pričom $a = b$. potom vieme spraviť operácie tak, aby sme skončili s viac ako $b$ bielymi vrcholmi.

Dôkaz. Opäť každý vrchol z $C$ vyberieme so šancou $p = \frac{1}{2}$. Avšak tentokrát dostaneme, že stredná hodnota prírastku bielych vrcholov je $0$. V zadaní sme začínali s viac čiernymi vrcholmi, preto musí existovať do našej terajšej situácie (kde je rovnaký počet bielych a čiernych vrcholov) postupnosť aktivácií vrcholov z $C$, ktorá zvyšuje počet bielych vrcholov. Keď však túto istú postupnosť aktivácií aplikujeme na terajšie rozloženie s rovnakým počtom čiernych a bielych, dostaneme sa do počiatočného rozdelenia, a teda táto postupnosť zníži počet bielych vrcholov. Ale keďže v strednej hodnote nám náhodný výber dáva počet pridaných bielych vrcholov $0$, tak musí existovať aj taká postupnosť aktivácií vrcholov z $C$, čo zvýši počet bielych vrcholov. $\square$

Opakovaným používaním Lemmy 1, prípadne jedným použitím Lemmy 2 dostávame, že existuje postupnosť premiešaní taká, že po ich dokončení bude existovať viac bielych ako čiernych vrcholov.