1. Kapitán Modrobrada Súperí (κ ≤ 1) vzorové riešenie

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\) až \(2k+1\) (kde k je jedno z čísel \(1\) až \(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.