V tenisovom turnaji hrajú každí dvaja hráči proti sebe presne raz. Keď sa turnaj skončí, každý hráč si napíše na zoznam mená hráčov ktorých porazil a tiež tých, ktorí boli porazení niektorým hráčom ktorého on sám porazil. Indukciou ukážte, že aspoň jeden hráč má na zozname meno každého iného hráča. Potom skúste argument ktorý indukciu nepoužíva.
Situáciu si môžeme predstaviť tak, že hráčov si znázorníme vrcholmi a pospájame ich šípkami. Každý hráč je spojený s každým a šípka ukazuje z víťaza na porazeného. Chceme ukázať, že existuje vrchol z ktorého sa dá dostať do všetkých ostatných tak, že prejdeme najviac po dvoch šípkach.
Možno sa oplatí spomenúť, že grafu takéhoto typu sa skutočne hovorí turnaj.
Dôkaz indukciou.
V podgrafe na $n$ vrcholoch je taký vrchol, že sa z neho dá dostať do každého najviac v dvoch krokoch. Ak pridáme nový vrchol, treba sa zamyslieť nad tým, čo by znamenalo, že do tohoto nového vrcholu sa dvoma krokmi nedá dostať. (Inak: Pozerajme sa na vrcholy, do ktorých sa dá v menšom grafe dostať jedným krokom alebo dvoma krokmi a ich vzťah k novému vrcholu.)
Spoiler:
Ľahko sa skontroluje, že to platí pre dva vrcholy.
Indukčný krok: Predpokladajme, že tvrdenie platí pre $n$ vrcholov. Majme takýto graf $G$ na $n+1$ vrcholoch. Označme si jeden z vrcholov $x$.
Ak sa pozeráme iba na ostatné vrcholy, teda na podgraf $G-\{x\}$ tak podľa indukčného predpokladu tam existuje vrchol $v$, z ktorého sa do ďalších vrcholov dá dostať v najviac dvoch krokoch.
Ak sa dá dostať v celom grafe $G$ v dvoch krokoch z $v$ do $x$, tak $v$ je hľadaný vrchol.
Predpokladajme teda, že z $v$ do $x$ neexistuje cesta dĺžky najviac dva. Tvrdíme, že potom $x$ má požadované vlastnosti.
Ak z $v$ do $x$ neexistuje cesta dĺžky najviac dva, tak to špeciálne znamená, že hrana medzi $v$ a $x$ je orientovaná v smere $x\to v$. Teda do $v$ sa vieme dostať jediným krokom.
Ešte sa treba pozrieť na ostatné vrcholy. Nech $y$ je ľubovoľný vrchol z $G-\{x,v\}$, chceli by sme ukázať, že z $x$ do $y$ sa dá dostať cestou dĺžky najviac dva.
Podľa indukčného predpokladu máme cestu z $v$ do $y$ dĺžky najviac dva. Ak máme cestu dĺžky jedna, t.j. hranu $v\to y$, tak sa z $x$ do $y$ dá dostať v dvoch krokoch: $x\to v\to y$.
Zostáva teda možnosť, že z $v$ do $y$ sa ide cez nejaký iný vrchol $z$, t.j. máme $x\to z\to y$. Čo vieme povedať o hrane medzi $x$ a $z$? Ak by bola v smere $z\to x$, tak by sme mali cestu dĺžky dva $v\to z\to x$. My sa zaoberáme prípadom, kedy takáto cesta neexistuje. To ale znamená, že máme $x\to z$. A dostaneme hľadanú cestu dĺžky dva $x\to z\to y$ z $x$ do $y$. $\square$
Dôkaz bez indukcie.
Hint: Skúste sa pozrieť na hráča s maximálnym počtom víťazstiev. (Aspoň jeden taký hráč tam je.)
Spoiler:
Ukážeme, že hráč s najväčším počtom víťazstiev má na svojom zozname všetkých hráčov.
Nech hráč $x$ má maximálny počet víťazstiev. Postupujme sporom - predpokladajme, že by existoval hráč $y$, ktorého $x$ nemá na zozname.
To znamená, že hráč $y$ porazil hráča $x$. A súčasne hráč $y$ porazil všetkých hráčov, ktorých porazil $x$ (inak by bol na zozname). Teda $y$ má aspoň o jedno víťazstvo viac ako $x$, čo je spor. $\square$
Pridám ešte nejaké linky, kde sa dá pozrieť riešenie toho istého problému (a možno je zapísané rozumnejšie).