8. Kanianske Metro Spojazdnené vzorové riešenie

Na začiatok uvažujme prípad, kedy všetky linky majú spoločnú zastávku \(Z\). Vtedy zastávka \(Z\) bude nadzemná a zvyšné podzemné, čím zjavne každá linka bude obsahovať zastávky oboch typov.

Teraz predpokladajme, že nemáme zastávku, ktorá je na všetkých linkách. Zjavne v takom prípade máme aspoň tri linky. Uvažujme teda ľubovoľné dve linky \(a\), \(b\) a označme si ich spoločnú zastávku ako \(Z\). Vieme, že niektorá linka zastávkou \(Z\) neprechádza – označme si ju \(c\). Ďalej si označme spoločnú zastávku liniek \(a\), \(c\) ako \(Y\) a spoločnú zastávku liniek \(b\), \(c\) ako \(X\). Zastávky \(X\), \(Y\) a \(Z\) budeme spoločne nazývať ako centrum.

Naša konštrukcia vyzerá nasledovne: nadzemné zastávky budú práve tie zastávky, ktoré sú na linkách \(a\), \(b\), \(c\) a zároveň nie sú v centre. Teraz ukážeme, že táto konštrukcia je správna. Každá z liniek \(a\), \(b\), \(c\) má zastávky oboch typov. Zoberme si linku \(l\) rôznu od \(a\), \(b\), \(c\). Ak majú linky \(a\), \(l\) spoločnú nadzemnú zastávku, tak linka \(l\) môže mať najviac dve ďalšie zastávky nadzemné – najviac po jednej na linkách \(b\), \(c\); teda linka \(l\) musí mať aj podzemnú zastávku. Ostáva prípad, kedy linky \(a\), \(l\) majú spoločnú podzemnú zastávku, bez ujmy na všeobecnosti nech je to zastávka \(Z\). Potom linka \(l\) neprechádza zastávkou \(Y\), ani \(X\), lebo s linkou \(a\), ani \(b\), nemôže mať spoločné dve zastávky. Preto spoločná zastávka liniek \(l\), \(c\) leží mimo centra, a teda je nadzemná. Linka \(l\) teda vo všetkých prípadoch má zastávky oboch typov, čím je náš dôkaz ukončený.

Komentár k riešeniu

Riešenie, ktoré uvádzame, je napísané v čistej forme – teda bez omáčok okolo, ako naň prísť. Preto k nemu na záver povieme nejaké komentáre. Takéto riešenia sa aj ľahko opravujú, lebo v nich pekne vidno dôležité kroky.

Riešenia takýchto úloh vyzerajú tak, že opíšeme spôsob, ako rozdelíme zastávky na dva typy a potom ukážeme, že toto naše rozdelenie je správne. Nájsť také rozdelenie vyžaduje zväčša veľa skúmania, hrania sa, kreslenia si, ... a potom všímania súvislostí, pravidelností a systémov. Na začiatok môže pomôcť skúsiť si kresliť linky postupne. Prvé dve sa dajú nakresliť jednoznačne: musia mať spoločnú práve jednu zastávku \(Z\). Tretia môže prechádzať zastávkou \(Z\) alebo každú s prvých dvoch liniek môže pretínať v iných zastávkach. Týmto dostávame nejakú štruktúru, ako to musí v našich linkách vyzerať. A na niečom takom vieme založiť riešenie, napr. naše vzorové.

Pri hľadaní konštrukcie v takýchto úlohách sa oplatí mať na pamäti nasledovnú vec. Čím jednoduchšie rozdelenie zastávok vymyslíme, tým ľahšie sa nám bude písať riešenie, a taktiež sa nám môže jednoduchšie ukazovať jeho správnosť. Jednoduchý systém však neznamená ľahko objaviteľný. Často sa za ním skrýva nejaká netriviálna myšlienka, prípadne nejaký trik. No ak sa nastavíme na hľadanie niečoho takého pekného, môže nám to uľahčiť riešenie. Ak si chcete hľadanie jednoduchých opisov vyskúšať, môžete si skúsiť vyriešiť 14. úlohu 2. zimného kola KMS 2007/08 alebo úlohu z celoštátneho kola MO 65-A-III-3.