Zadanie

Kapítan Modrobrada sa plaví za kolonizáciou Ameriky. Jeho posádka sa rozhola skrátiť si dlhú plavbu turnajom v pretláčaní sa.

Posádka lode má \(32\) námorníkov. Prvý deň hral každý námorník práve \(1\) zápas (každý zápas hrajú vždy dvaja námorníci proti sebe). Druhý deň takisto hral každý námorník práve \(1\) zápas. Ukážte, že po týchto dvoch dňoch vieme vybrať \(16\) námorníkov tak, že žiadni dvaja z nich proti sebe ešte nezápasili, a to bez ohľadu na to, ako námorníci zápasili v prvé dva dni.

Našou úlohou je nájsť skupinu \(16\) námorníkov, ktorí proti sebe ešte nezápasili, bez ohľadu na to, ako vyzerali zápasy počas prvých dvoch dní. Keďže každý námorník odohral zápasy s práve dvomi rôznymi námorníkmi, môžeme si všetkých námorníkov usporiadať akoby do kruhu tak, že vedľa námorníka sa budú nachádzať námorníci, s ktorými zápasil (jeden vpravo a druhý vľavo). Takto budú všetci námorníci rozdelení na niekoľko (môže byť aj jeden) samostatných kruhov.

Teraz sa budeme snažiť ukázať, že v každom z týchto kruhov je párny počet námorníkov. Ukážeme si, prečo v jednom kruhu nemôže byť nepárny počet námorníkov. Predstavme si, že máme kruh s nepárnym počtom námorníkov. Očíslujme si námorníkov číslami \(1\)\(2k+1\) (kde k je jedno z čísel \(1\)\(15\)) v takom poradí, v akom sú v kruhu, pričom námorník \(1\) má vpravo od seba svojho súpera z prvého dňa (jemu dáme číslo \(2\) a pokračujeme v číslovaní v tomto smere). Námorník, s ktorým námorník číslo \(1\) súperil počas druhého dňa bude mať teda číslo \(2k+1\). Môžeme si všimnúť, že každý námorník s nepárnym číslom má vľavo od seba súpera z druhého dňa. Námorníci \(1\) a \(2k+1\) majú obaja nepárne čísla, takže by obaja mali mať vľavo od seba svojho súpera z druhého dňa. To ale znamená, že námorník \(2k+1\) musel počas druhého dňa odohrať dva zápasy. To je ale spor so zadaním, a preto vedľa seba nemôžu stáť dvaja námorníci s nepárnymi číslami. A z toho už vyplýva, že v každom z kruhov je párny počet námorníkov.

Ak z každého kruhu zoberieme každého druhého námorníka, budeme ich mať presne polovicu zo všetkých, čiže \(16\). Títo námorníci proti sebe určite nezápasili, lebo každý zápasil len s tými, čo sú v cykle hneď vedľa neho. Našli sme teda \(16\) námorníkov, ktorí vyhovujú zadaniu, čím sme dokázali to, čo sme mali.

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ť.