Úloha na tento týden

Tento semestr budeme společně řešit problémy z knihy pana Lovásze: Combinatorial problems and exercises. Na konci jednoho semináře si řekneme zadání, na začátku příštího někdo, kdo problém vyřešil, řekne řešení. Tady na webu se kromě zadání dočtete i malou nápovědu.

1) Dokažte, že R_k(3) <= [e.k!]+1 ([x] značí celou část z x). Tj. ukažte, že jakkoliv obarvíme hrany úplného grafu s [e.k!]+1 vrcholy pomocí k barev, vždy dostaneme jednobarevný trojúhelník. Také dokažte, že pro k = 2 a 3 nastává rovnost.

Nápověda

2) Obarvíme hrany úplného grafu K_n (n >= 3) dvěma barvami. Dokažte, že existuje hamiltonovská kružnice, která je buď jednobarevná, nebo sestává ze dvou jednobarevných úseků.

Nápověda

3+4) Obarvíme body v rovině dvěma barvami. a) Dokažte, že nemusí existovat jednobarevný rovnostranný trojúhelník se stranou dělky jedna. b) Dokažte, že naproti tomu musí existovat jednobarevný trojúhelník se stranami odmocnina ze 2, odmocnina z 6, pi. Protože je úložka (zvláště část b) trochu těžší, rozdělíme ji do dvou částí.

  1. Pokud nenajdeme jednobarevný rovnostranný trojúhelník se stranou délky jedna, tak ho najdeme se stranou délky odmocnina ze tří.

    Nápověda

  2. Pokud najdeme jednobarevný rovnostranný trojúhelník se stranou délky jedna, pak také najdeme jednobarevný trojúhelník se stranami délek 1, a, b; kdykoli je splněna trojúhelníková nerovnost.

    Malá nápověda Větší nápověda

5) Označme m=2n-1. Uvažme m-tici přirozených čísel f1, ..., fm takových, že pro všechna i platí 1 <= fi <= i.

a) Dokažte, že lze vybrat neklesající podposloupnost délky n. Tj. že existuje 1 <= a1 < a2 < ... < an <= m, že fa1 <= fa2 <= ... fan.

b) Dokažte, že pro m=2n-1-1 to už neplatí.

Tip: zkuste napřed b-čko. Jednak je lehčí, jednak třeba něco napoví.

Nápověda

6) Rozkladem přirozeného čísla budeme rozumět jeho zápis jako součet (libovolného počtu) přirozených čísel, přičemž nám nezáleží na pořadí. Kupříkladu 3 má tři rozklady: 3, 2+1 a 1+1+1.

Dokažte, že rozkladů čísla n na nejvýše k sčítanců je přesně tolik, kolik je rozkladů čísla n na libovolný počet sčítanců, z nichž každý je nejvýše roven k.

Nápověda

7) Pokud je $G$ rovinný 4-regulární graf, pak lze jeho hrany orientovat tak, že se u každého vrcholu pravidelně střídají hrany dovnitř a hrany ven---tj. dvě protilehlé jdou dovnitř, druhé dvě protilehlé ven.

Nápověda