Zadanie
Po Jožovi ostalo v KMS veľa roboty, medzi iným rozdeliť vedúcim opravovanie riešení. Máme \(n\) úloh, z každej \(k\) riešení na opravovanie a \(k\) vedúcich KMS. Jožo pred odchodom, nestíhajúc, dal každému vedúcemu \(n\) náhodných riešení. Vedúci by chceli, aby to bolo rozdelené , t. j. nech každý z nich opravuje práve jedno riešenie z každej úlohy. Preto sa rozhodli, že si budú meniť riešenia. Dvaja vedúci sú ochotní vymeniť riešenie za riešenie, ak každý z nich dostane riešenie úlohy, z ktorej riešenie ešte nemá. Dokážte, že bez ohľadu na to, ako boli na začiatku rozdané riešenia, si takýmito výmenami môžu prerozdeliť riešenia spravodlivo.
Nazvime stavom nejaké konkrétne rozdelenie riešení medzi vedúcich také, že každý vedúci má \(n\) riešení. Uvedomme si, že počet rôznych stavov, ktoré môžu nastať, je konečný, pretože vedúcich, riešení a úloh je konečný počet.
Náš cieľový stav je taký, že každý vedúci má \(1\) riešenie z každej úlohy. Označme si číslom \(Z_i\), počet zlých riešení ktoré má \(i\)-ty vedúci, teda rozdiel počtu riešení (\(n\)) a počtu rôznych úloh, ktoré má \(i\)-ty vedúci. Číslom \(Z\) označíme počet zlých riešení, ktoré majú vedúci dokopy (\(\sum_{i=0}^{n} Z_i\)). Cieľový stav si vieme zadefinovať tak, že \(Z=0\) (rozmyslite si). Chceme dokázať, že v každom necieľovom stave existuje výmena, ktorá zmenší \(Z\), čím ukážeme, že vždy vieme dosiahnuť cieľový stav.
Zoberme si vedúceho, ktorého \(Z_i\) je najväčšie, teda toho, ktorý má najviac zlých riešení a nazvime ho smoliar. Smoliar má najviac zlých riešení, čo znamená, že má najmenší počet rôznych úloh. Z nejakej úlohy má smoliar aspoň \(2\) riešenia, povedzme si, že je to úloha 1 (nezáleží na tom, ktorá je to presne). Keďže má aspoň \(2\) riešenia úlohy 1, tak existuje vedúci (volajme ho antismoliar), ktorému chýba riešenie úlohy 1. Vieme, že \(Z_{smoliar} \ge Z_{antismoliar}\). Z toho vyplýva, že antismoliar má riešenie nejakej úlohy (nech je to úloha 2), ktoré smoliarovi chýba (keďže má aspoň toľko rôznych úloh, koľko smoliar a úlohu 1 nemá). Výmenou medzi smoliarom a antismoliarom úloh 1 a 2 sa \(Z_{smoliar}\) zmenší o \(1\) a \(Z_{antismoliar}\) sa buď zmenší o \(1\) (ak úlohu 2 mal viac krát) alebo zachová (ak úlohu 2 mal len raz). Teda sa \(Z\) zmenší o \(1\) alebo \(2\). Keďže v každom necieľovom stave existuje vedúci, ktorý má \(Z_i\) najväčšie, tak vždy vieme spraviť výmenu tak, aby sa \(Z\) zmenšilo, a teda postupne výmenami dosiahnuť cieľový stav.
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ť.