5. príklad - Vzorové riešenie
Zadanie
Okolo autobusu je vo vrcholoch pravidelného 9-uholníka rozostavených 9 vedúcich. Ak vezmeme hocijakú dvojicu vedúcich, tak buď pomohol prvý vedúci druhému, alebo druhý prvému. Vedúci však sú veľmi dobre pripravení na krízové situácie, a preto každý vedúci najprv pomohol vedúcemu, ktorý bol hneď naľavo od neho. Dokážte, že v takomto prípade existuje trojica vedúcich A,B,C taká, že A pomohol B, B pomohol C a C pomohol A.
Vzorové riešenie
Túto úlohu budeme riešiť sporom. To znamená, že najprv budeme predpokladať, že máme také rozloženie vedúcich a toho ako si pomáhajú, v ktorom neexistuje trojica vedúcich ABC kde A pomáha B, B pomáha C a C pomáha A. A potom sa pokúsime nájsť nejaký protiklad/spor a tým dokázať, že takéto rozloženie nemôže existovať.
Takúto trojicu kde si vedúci pomáhajú do kruhu nazvime pomáhajúcou trojicou. Vedúcich si označíme KLMNOPQRS kde K pomáha L, L pomáha M a tak ďalej až po S pomáha K. Všimnime si, že keďže predpokladáme, že neexistuje pomáhajúca trojica, musí K pomáhať M, lebo inak by KLM bola pomáhajúca trojica. Podobne teraz K musí pomáhať aj N aby nevznikla pomáhajúca trojica KMN. Toto vieme povedať aj pre všetkých vedúcich OPQR. K musí pomáhať O aby nevznikla KNO pomáhajúca trojica. Potom K musí pomáhať postupne aj P,Q,R aby nevznikli pomáhajúce trojice KOP, KPQ, KQR. Teraz však K pomáha R, R pomáha S (S je naľavo od R) a S pomáha K (K je naľavo od S). Toto je spor, nakoľko sme predpokladali, že nemáme ani jednu pomáhajúcu trojicu a napriek tomu sme jednu našli. To znamená, že nech si pomáhajú ľubovoľne, vždy musí existovať trojica vedúcich ABC kde A pomáha B, B pomáha C a C pomáha A.
