Zk. 2009-06-12 - Kratochvíl

Snad všechny dnešní příklady jsem už někde v historii fóra viděl, takže zadání popíšu jen tak lehce. Upřesnění a případně i výsledky budou možná následovat později.

1. Dpolňte LO 3×6 na LČ 6×6 (nebo dokažte, že to nejde).

2. Napište vytvořující funkci pro řadu (2,2,3,3,4,4,5,5,...).

3. Najděte min. řez v grafu.

4. Které z následujících množinových systémů mají SRR? (Následovaly 3 množinové systémy o max. 5 množinách o max. 4 prvcích.)

5. Dokažte, že pro každý k-regulární graf G platí, že k_v(G) = k_e(G).

6. Dokažte, že pro každé k, n existuje N, že v každé množině bodů v rovině o velikosti N, jejíž dvojice bodů určují max. k směrů, existuje n bodů, které leží na 1 přímce.

Příklad řešení:

1. LO lze vždy doplnit na LČ - nejlépe to tam prostě nějak ručně doplnit.

2. Standardní řešení - vyjdu z (1,1,1,1,...) a postupně funkci upravuji.

3. Najdu max. tok, ten se rovná min. řezu, najdu takový min. řez (min. řezem se myslí řez o min. kapacitě).

4. Pokud SRR existuje, stačí jej napsat. Pokud neexistuje, stačí napsat množinu množin, které nesplňují Hallovu podmínku.

5. Lze řešit buď rozborem případů pro k_v(G) nebo pomocí F-F a Mengerovy věty (vím-li, že existuje k hranově disjunktních hran, potom tyto cesty jsou také vrcholově disjunktní - kdyby ne, tak vrchol, ve kterém se protínají musí mít stupeň 4).

6. Přesné zadání: Dokažte tvrzení: Pro každá dvě přirozená čísla k a n existuje přirozené číslo N s následující vlastností. Pokud pro nějakou množinu M obsahující N bodů v rovině platí, že přímky určené dvojicemi bodů z M určují nejvýše k směrů, pak alespoň n bodů z M leží na jedné přímce.
   Řešení A: Přes Ramseyovu větu o barvení k-tic - barvy jsou směry, barvíme dvojice, vyjde nám, že existuje n bodů, ze kterých vybereme libovolný bod a ten s libovolným jiným bodem v této množině určuje tentýž směr. Z analytické geometrie víme, že přímku lze jednoznačně určit bodem a směrem, tedy všechny body jsou na jedné přímce.
   Řešení B: Vybereme libovolný pevný bod a proložíme přímky všemi ostatními body. Směrů (tedy i přímek) musí být k, ale bodů máme N, tedy musí existovat přímka (Dirichlet), že je na ní >= N/k bodů. zvolíme-li N dostatečně velké, pak N/k > n.

Toto jsou pouze myšlenky řešení. V písemce je to potřeba podrobněji rozebrat.