4. Kamarátov Magalhães Stratil vzorové riešenie

Pri taktom type úloh môžu nastať len dve možnosti: buď tvrdenie v úlohe platí – vtedy ho treba dokázať – alebo naopak existuje takzvaný protipríklad, konkrétna situácia, v ktorej tvrdenie zo zadania neplatí. Pre vyriešenie úlohy v tomto prípade nám stačí nájsť aspoň jeden konkrétny protipríklad, pre ktoré tvrdenie neplatí, a – samozrejme – vysvetliť, prečo protipríkladom naozaj je.

Zo začiatku riešenia takýchto úloh je dobrým zvykom, aj na matematickej olympiáde, si nakresliť niekoľko konkrétnych prípadov možných kamarátstiev a na ich základe sa snažiť všimnúť si niektoré okolnosti, ktoré v danej úlohe platia. Tiež sa oplatí skúsiť nájsť nejaký protipríklad, zákerné rozmiestnenia kamarátov, ktoré sťažia alebo znemožnia rozdelenie do dvojíc.

Napríklad pri tejto úlohe sme si mohli po chvíľke kreslenia konkrétnych príkladov všimnúť, že pri nepárnom počte námorníkov by sme ich nevedeli do člnov rozumne usporiadať. Do dvojmiestnych člnov sa nepárny počet námorníkov proste nezmestí. To je ale asi tak všetko, čo sa nám v tejto fáze riešenia úlohy podarilo odhaliť. Následne sme sa zrejme pokúšali nejakým rozumným spôsobom tvrdenie dokázať, napríklad opísať všeobecný postup, ktorým nájdeme správne dvojice. Nejako však žiaden z daných spôsobov k riešeniu neviedol.

Vtedy, ak žiadna metóda nevedie k vytúženému dôkazu, je vcelku rozumné sa pozrieť na úlohu z opačného uhla pohľadu a skúsiť nájsť protipríklad. Pretože rovnako tvrdenie z úlohy nemusí platiť a vtedy riešením je ukázať ten prípad, kedy riešiteľná nie je.

Samotné riešenie – protipríklad exituje

Pri hľadaní protipríkladu je tiež dobrým nápadom vychádzať z toho, čo sme už objavili, ale použiť to proti úlohe samotnej. Napríklad sme zistili, že pri nepárnom počte námorníkov by úloha riešenie nemala. Preto pri hľadaní protipríkladu sa budeme usilovať nakombinovať kamarátstva tak, aby nám vznikla nejaká uzavretá skupina nepárneho počtu kamarátov. Vytvoriť takúto skupinu sa nám však nejak nedarí. Vždy v takejto uzavretej skupine skončí aspoň jeden námorník s najviac dvomi kamarátmi (rozmyslite si prečo). My pritom potrebuje kamarátstva tri. To nám môže robiť problémy, pretože nám to spojí uzavretú skupinu s ostatnými.

Jedine, že by nám to ani až tak nevadilo. Kamarátstvo, ktoré vychádza z nepárnej skupiny námorníkov, musí byť isto vybrané do člna. Máme tak teda dvojicu kamarátov, ktorá musí byť spolu v člne pri každom rozdelení. Preto si vieme zobrať tri takéto „uzavreté“ skupiny a toho námorníka s nedostatočným počtom kamarátov spojiť s jedným námorníkom, ktorý je „niekde mimo od ostatných“. Tak nám vzniknú tri skupiny po päť námorníkoch, ktoré sú spojené s jedným námorníkom v strede ako na obrázku. Na ňom sú námorníci vyznačený bodkami a čiarou sú spojení tí, ktorí sa kamarátia. Pri takomto rozložení nevieme námorníkov popárovať tak, aby každý námorník bol v člne so svojím kamarátom. Pretože „osamotený“ námorník v strede si môže zobrať do člna len jedného kamaráta, a tým pádom nám ostanú dve pätice námorníkov, ktorí sa kamarátia len medzi sebou. A nepárny počet námorníkov do dvojíc nevieme rozdeliť.

Vieme to napraviť?

Hoci tvrdenie zo zadania úlohy neplatí, môžeme sa pozrieť, ako ďaleko od toho má. Koľko ďalších rozložení kamarátstiev vieme nájsť, pre ktoré námorníci nepôjdu popárovať? A ako to bude vyzerať, ak námorníkov bude viac? Nevieme na ich kamarátstva uložiť nejakú podmienku navyše, ktorá by nám zaručila, že pôjdu popárovať?

Keď sa pozrieme na náš protipríklad, tak tam nájdeme dvojicu námorníkov, ktorí ak by sa prestali kamarátiť, tak by sa sieť kamarátstiev rozpadla na dve izolované skupiny. Odborne sa takáto dvojica nazýva most. Pochopiteľne, samotná prítomnosť mostu nám úlohu ešte nepokazí – skúste si nájsť také rozloženie kamarátstiev, ktoré obsahuje most, ale námorníci v ňom popárovať idú. Avšak, pokiaľ most zakážeme, tak už je zaručené, že námorníci vždy popárovať idú. Presne toto hovorí výsledok teórie grafov známy pod názvom Petersenova veta, ktorý je dôsledkom Tuttovej vety, ktorá presne hovorí, kedy má graf úplné párovanie. Oba tieto výsledky však ďaleko presahujú rámec Korešpondenčného matematického seminára a dokázať ich by bolo priveľa aj na 10. úlohu. Ich dôkaz zaberie vyše hodiny intenzívnej prednášky.

Komentár

Mnohým riešiteľom sa nepodarilo úlohu vyriešiť. Dostali sme veľa „dôkazov“, že námorníkov možno vždy rozdeliť do dvojíc. Väčšina takýchto riešení bola principiálne nesprávne, ani by sme sa ich neodvážili nazvať dôkazmi. Cieľom tejto úlohy bolo postaviť vás pred tvrdenie, ktoré neplatí, ale nie je to zjavné na prvý pohľad. Skúsiť si dokázať neplatné tvrdenie je veľmi poučné zvlášť pre tých z vás, čo s dôkazmi začínate. Ľahšie tak uvidíte, kde vaša argumentácia zlyhala a pomôže vám to vyvarovať sa nedôsledným dôkazom pri ďalších úlohách. Okrem toho, pokiaľ máte ťažkosti s dokazovaním tvrdenia, tak je veľmi užitočná schopnosť vedieť prepnúť svoje zmýšľania, pozrieť sa na tvrdenie z druhej strany a pokúsiť sa ho vyvrátiť. To, že niečo nevieme dokázať, môže znamenať, že to neplatí.

Častou argumentáciou bolo, že keďže nemôže existovať skupina nepárne veľa námorníkov, ktorí sa kamarátia medzi sebou, tak námorníci musia ísť popárovať. Je pravda, že ak by sme takú skupinu s nepárnym počtom námorníkov mali, párovanie by nebolo možné. To však vôbec nič nehovorí o tom, keď takú skupinu nemáme – nijako nám to nezaručuje existenciu párovania. Hovoríme tomu, že neexistencia takejto nepárnej skupiny je nutnou podmienkou. To znamená, že ak táto podmienka nie je splnená, naše tvrdenie nemôže platiť. Pokiaľ nutná podmienka je splnená, tak nezaručuje ešte platnosť tvrdenia. Napr. nutnou podmienkou na to, aby číslo bolo deliteľné \(10\)-timi je, aby bolo párne. Ak je však číslo párne, nemusí byť ešte deliteľné \(10\)-timi.

Objavilo sa aj niekoľko serióznejších pokusov. Niektorí riešitelia sa snažili miesto hľadania dvojíc kamarátov najprv zrušiť každému námorníkovi dve kamarátstva. Hoci to môže na prvý pohľad vyzerať sľubne, nejde o nič prevratné – je to len inak preformulovaná úloha, ktorá je podobne náročná. Iní riešitelia sa zas pokúšali zoradiť všetkých námorníkov do radu, aby vedľa seba stáli vždy kamaráti alebo hľadali podobné štruktúry v ich kamarátstvách. Pri dôkaze ich existencie však nepostupovali dôsledne, zabudli na dôležitý prípad, ktorý im pokazil argumentáciu. Odhliadnuc od toho, nájdenie podobných štruktúr vie byť dosť náročné a pre mnohé z nich nie zú známe žiadne rozumne použiteľné postačujúce podmienky.