Úkoly z Kombinatoriky a grafů, 8. série

Veškerá tvrzení precizně zdůvodněte.

(8.1) Formule 3, 3-SATu je logická formule v konjunktivní normální formě (CNF), kde a) každá proměnná se vyskytuje ve formuli právě třikrát, b) každá klauzule formule má právě tři literály. Dokažte, že libovolná formule tohoto tvaru je vždy splnitelná. 4 body

(8.2) Dokažte, že Fanova rovina je jediná (až na izomorfismus) konečná projektivní rovina řádu 2. 3 body

(8.3) Nechť X je množina s n^{2} + n + 1 prvky a P ⊆ \binom{X}{n+1} množina (n + 1)- prvkových podmnožin X, taktéž velikosti n^{2} + n + 1, kde pro každé dva různé prvky p_{1}, p_{2} ∈ P platí |p_{1} ∩ p_{2}| ≤ 1. Dokažte, že pro každé dva různé prvky x_{1}, x_{2} ∈ X existuje právě jedna p ∈ P taková, že x_{1}, x_{2} ∈ p. Dále dokažte, že každý bod x ∈ X leží v právě n + 1 množinách z P. 5 bodů