Matematické Fórum

kocourOggy · 18. 06. 2018 18:22

Uvažujme turnaj, jehož účastníci hrají každý s každým a pouze jednou.
"Hráč x porazil hráče y" budeme značit jako x > y. Cyklem délky n rozumíme situaci, kdy máme hráče h_1, h_2,..., h_n takové, že h_1 > h_2 ... > h_n > h_1
Dokažte, že jestli se ve výsledcích turnaje najde cyklus délky n, pak se tam najde i cyklus délky 3.
=========================================================
Indukcí podle délky cyklu. V(n) <=> "Existuje-li cyklus délky n>2, existuje i cyklus délky 3"

V(3).... platí triviálně.
Předpokládejme platnost V(n) pro nějaké n. Zajímá nás platnost V(n+1)... uvažujme cyklus h_1 > h_2 > h_3 > ... h_n+1 > h_1. Jak dopadl souboj h_1 a h_3? Pokud h_3 > h_1 potom máme cyklus délky 3: h_1 > h_2 > h_3 > h_1.

Jestliže naopak h_1 < h_3, tak lze h_2 z původního cyklu vynechat a dostaneme cyklus délky n h_1 > h_3 > ... > h_n > h_n+1 > h1, na který lze použít indukční předpoklad.

Jak si prosím ospravedlnit bezproblémové odstranění h_2 z cyklu? Co když zrovna h_2 tvořil cyklus h_2 > h_3 > h_4 > h_2 o který jsem ale přišel v okamžik kdy jsem h_2 odstranil?

Stýv · 18. 06. 2018 21:36

Když tam je cyklus délky n bez h_2, tak je tam i nějaký cyklus délky 3 bez h_2.

kocourOggy · 18. 06. 2018 22:48

↑ Stýv:
No jo vlastně. Děkuju :) Sám bych si to asi jen tak neuvědomil.

Jinak musím se opravit... "Jestliže naopak h_1 < h_3, tak lze h_2 z původního cyklu vynechat a dostaneme cyklus délky" ten zobáček měl být naopak, tedy h_1 > h_3

Matematické Fórum

#1 18. 06. 2018 18:22

Matematická indukce k důkazu existence cyklu délky 3

#2 18. 06. 2018 21:36

Re: Matematická indukce k důkazu existence cyklu délky 3

#3 18. 06. 2018 22:48

Re: Matematická indukce k důkazu existence cyklu délky 3

Zápatí