Zadanie
V KMS je niekoľko vedúcich a niektoré dvojice sa spolu kamarátia. Namiesto toho, aby si užívali pokojné Vianočné sviatky, sa radšej hádajú, či je krajšia fialová alebo modrá farba. Na začiatku si každý vedúci myslí, že krajšia je fialová. Občas sa stane, že jeden vedúci zorganizuje stretnutie, ktorého sa zúčastní on a všetci jeho kamaráti. Po tomto stretnutí sa všetkým zúčastneným vedúcim zmení názor. Je možné bez ohľadu na to, ako sa vedúci kamarátia, že po niekoľkých stretnutiach si budú všetci vedúci myslieť, že je krajšia modrá?
Ako vo veľa úlohách, aj v tejto bude užitočná matematická indukcia. My budeme robiť indukciu na počet vedúcich.
Prvý krok indukcie je ukázať naše tvrdenie pre triviálny prípad – keď máme len jedného vedúceho. Ten je sám a nemá žiadnych kamarátov, takže keď ho pozveme na stretko, názor sa zmení len jemu. Easy.
Zaujímavejší je prípad, keď máme vedúcich viac ako jedného. Vtedy môžeme využiť indukčný predpoklad, že pre všetky skupiny menších vedúcich tvrdenie platí – t. j. že vieme zvolať stretká tak, aby sa všetkým zmenil názor. Vieme preto jedného vedúceho, napr. Vodku, vynechať a zvolať stretká tak, že sa zmení názor všetkým vedúcim okrem Vodku. Pri ňom mohli nastať dve veci, buď sme názor zmenili aj Vodkovi a vyhrali sme, alebo sa nám to nepodarilo.
Ak sa nám to nepodarilo, všimneme si, že sme nemuseli vynechať Vodku ale mohli sme vynechať hocijakého vedúceho. Keby sme pri vynechaní iného vedúceho, napríklad Mariána, mali šťastie, že po zmenení názoru všetkých ostatných by sa zmenil aj Mariánovi názor, tak sme znova vyhrali.
Ak nie, tak to znamená, že pre ľubovoľného vedúceho dokážeme zmeniť názor všetkým vedúcim okrem neho. Keď toto urobíme dvakrát s rôznymi vedúcimi – napríklad s Vodkom a Mariánom, tak Vodkovi a Mariánovi zmeníme názor a ostatným ho zmeníme dvakrát, čiže im ostane pôvodný názor. Keďže to vieme urobiť s ľubovoľnými dvoma vedúcimi, znamená to, že vieme zmeniť názor ľubovoľným dvom vedúcim.
Ak máme párny počet vedúcich, opäť je to jednoduché, pretože takto všetkým po dvojiciach dokážeme zmeniť názor na ten správny, že modrá je lepšia.
Už nám len ostáva prípad, že máme nepárny počet vedúcich. Keby sme vedeli zmeniť názor nepárnemu počtu vedúcich, mohli by sme pokračovať zvyšnými pármi, a zmeniť názor všetkým vedúcim. Najjednoduchšie by sme to mohli urobiť tak, že stretko zvolá taký vedúci, ktorý má párny počet priateľov. Otázka je, či taký vedúci existuje.
Odpoveď je áno, pretože keď sčítame priateľov všetkých vedúcich, zarátame každé priateľstvo dvakrát, a teda dostaneme párne číslo. Keby mal každý vedúci nepárny počet priateľov, tak by súčet priateľov všetkých vedúcich bol nepárny, čo je spor .
Preto naozaj môže tento vedúci zvolať stretko, tým zmeníme názor nepárnemu počtu vedúcich, a sme spokoní, pretože takto už naozaj dokážeme zmeniť názor každému vedúcemu.
Tým je dôkaz indukciou ukončený a naozaj vieme pre ľubovoľný počet vedúcich zvolať stretká tak, aby všetci zmenili názor.
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ť.