Zadanie
Klep, klep, kdo tam a co se tam dělá? Tady sé pije.
V zálive v Karibskom mori stredozemskom žije \(n\) sépií, kde \(n \geq 4\). Každá sépia má medzi zvyšnými nejaké kamarátky, pričom kamarátstva sú vzájomné. Občas sépie chytí nutkanie pochytať sa za ramená do kruhu. Každá sépia má dve ramená, každým môže chytiť nejakú inú sépiu za jej rameno. Žiadne dve sépie sa nechcú držať, pokiaľ nie sú kamarátky.
Vieme, že v zálive pre každé celé \(m\) také, že \(2 < m < n\), sa ku každým \(m\) sépiám, ktoré sa dokážu pochytať za ramená do kruhu, vie pridať nejaká zo zvyšných sépií tak, aby sa vzniknutá \((m+1)\)-tica opäť vedela pochytať za ramená do kruhu. To však nemusí znamenať, že nová sépia sa vie do kruhu priamo pridať, je možné, že sa ostatné sépie budú musieť nejakým spôsobom preusporiadať.
Jedného dňa sépia Septima (jedna spomedzi našich \(n\) sépií) prišla do zálivu, kde našla niekoľko sépií (aspoň tri, ale nevieme presne koľko), ako sa držia za ramená do kruhu (bez nej).
Dokážte, že pre každé \(m\), kde \(2 < m < n\), existuje \(m\)-tica sépií, ktoré sa dokážu držať do kruhu za ramená.
Označme počet sépií, o ktorých vieme, že vedia utvoriť kruh \(x\), pričom vieme iba, že \(2 < x < n\). Našou úlohou je ukázať, že určite existujú aj zo sépií zostrojiteľné kruhy veľkostí \(3\) až \(n\). Ukážme najprv, že určite bude existovať kruh najmenšej veľkosti, teda \(3\).
Predstavme si \(y\) sépií v kruhu veľkosti väčšej ako \(4\) a menšej ako \(n\). Ukážeme, že tento kruh vieme vždy zmenšiť (to, že môžeme zmenšiť aj kruh veľkosti \(4\) ukážeme potom trochu iným spôsobom). Určite existuje nejaká sépia, ktorá sa k nim vie pridať – teda je kamarátkou s aspoň dvomi z nich (inak by sa s ňou kruh vytvoriť nijako nedal). Vezmime teda nejaké dve jej kamarátky v kruhu. Ak sú na susedných miestach, tak spolu s ňou vedia vytvoriť kruh veľkosti \(3\). Inak delia zvyšok kruhu na dve časti (tieto dve sépie do zvyšku kruhu nerátame), z ktorých menšia musí mať veľkosť najviac \(y-4\) – ak by to tak nebolo, obe časti by museli byť väčšie, čo sa sčíta na aspoň \(2y-6+2 = 2y-4\) sépií celkovo, čo je určite viac ako \(y > 4\). Vezmime túto časť vrátane dvoch deliacich sépií, a kruh uzatvorme sépiou navyše, ktorá je kamarátkou ich oboch. Dostaneme kruh veľkosti najviac \(y-1\), teda sa nám kruh podarilo zmenšiť.
Dokážme už len, že vieme zmenšiť aj kruh veľkosti \(4\). Vieme, že určite existuje nová sépia, ktorá vie s týmito štyrmi sépiami utvoriť kruh veľkosti \(5\). Opäť platí, že bude mať medzi nimi aspoň dve kamarátky. Ak sú susedné, tvoria obe tieto kamarátky spolu s novou sépiou navzájom kruh veľkosti \(3\). Potrebujeme sa teda pozrieť na prípad, keď nie sú susedné. Nazvime tieto dve kamarátky \(A\) a \(B\). V kruhu veľkosti \(4\) musia byť nesusedné sépie oproti sebe, teda takto bude vyzerať cyklus: \(\ldots A, X, B, Y \ldots\) v poradí po obvode. Okrem toho vieme, že existuje nejaké poradie, v akom sú tieto sépie usporiadateľné do kruhu veľkosti \(5\), spolu s novou sépiou. Tri susedné miesta v tomto kruhu obsadí nová sépia s kamarátkami \(A\) a \(B\), takže sépie \(X\) a \(Y\) budú musieť byť na zvyšných dvoch miestach. Teda sépie \(X\) a \(Y\) musia byť kamarátky. To znamená, že sépie \(X\), \(Y\) a \(A\) tvoria kruh veľkosti \(3\). Čo bolo treba dokázať.
Vidíme, že určite vieme nájsť tri sépie tvoriace najmenší možný kruh. Ostáva nám len ukázať, že sa dajú vystavať aj všetky väčšie kruhy. To je pomerne triviálne – zo zadania priamo vyplýva, že ľubovoľný kruh nezahŕňujúci všetky sépie vieme zmeniť na kruh veľkosti o \(1\) väčšej, teda vieme skonštruovať všetky vyššie veľkosti.
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ť.