# Zkouška 26.5.2010 13:00 - Mareš

<{ForumPost(poster="Jookyn", timestamp=2010-05-26 16:17:02)}>
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.
<{/ForumPost}>

<{ForumPost(poster="amik", timestamp=2010-06-01 21:38:42)}>
*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
<{/ForumPost}>