Fórum studentů MFF UK

1) Dokázat odhad - 2^(n/2) <= R(n) <= 2^(2n)
2) # zobrazení {1...a} na {1...b}
3) Máme KPR, kde místo nultého axiomu (existence čtverce) máme: pro každé p z P: |p| >= 2. Jaké defektní KPR touto záměnou přibudou?
4) Pro každé k: (množinový systém (X,S) má SRR až na k množin <=> každé T podmnožina S |U T| >= |T|-k)
(*) Mohou existovat dvě různé mocniny dvojky, které jsou až na pořadí číslic v desítkové soustavě stejné? Dokázat

Přičemž jsme měli udělat příklad 1 a pak si vybrat 2 příklady z {2,3,4}, * byla spíš něco navíc.

*SPOILER ALERT* není to složité přijít na to sám

Nástin řešení:
1) máme v sešitě
2) pomocí principu inkluze a exkluze

3) rozebráním nejjednodušších případů se začne rýsovat toto:
a) jedna přímka procházející všechny body
b) -//- až na jeden mimo přímku - z něj vede n-1 přímek velikosti 2, každá do jednoho bodu na "původní" přímce
Stačí ukázat, že více přímek /p/ >= 3 by vytvořilo čtverec a pokud je jen jedna taková, nemůže mimo ní ležet více než 1 bod => postihli jsme všechny případy.

4) stačí X doplnit o k prvků a ty vložit do všech množin v S -> splňuje klasickou Hallovu podmínku -> utvoříme SRR a odebereme ty množiny, které mají jako reprezentanty ony doplněné prvky - těch je nejvýše K - z původních množin zbude alespoň n-k

*) jen napovím, že pořadí číslic nemění zbytek po dělení devíti