Sbírka matematických úloh

Minimální pokrytí

Úloha číslo: 3720

• Varianta

  minimální možnou mohutnost množiny \(Y \subseteq X\) takové, že \(\forall P \in \mathcal P: P \cap Y \not= \emptyset\).

• Nápověda

  Spočítejte dvěma způsoby počet indicencí mezi body pokrývací množiny a přímkami.

• Řešení

  Každý bod pokryje nejvýše \(n+1\) přímek, potřebujeme tedy alespoň \(\lceil\frac{n^2+n+1}{n+1}\rceil=n+1\) bodů.

  To že taková množina existuje dokazuje libovolná přímka \(Y\in\mathcal P\), protože každá jiná přímka z \(\mathcal P\) bude \(Y\) protínat.

• Odpověď

  Nejmenší hledaná množina \(Y\) má \(n+1\) bodů.

• Varianta

  minimální možnou mohutnost množiny \(Z \subseteq X\) takové, že \(\forall P \in \mathcal P: |P\cap Z| \geq 2\).

• Řešení

  Vezmeme-li za \(Z\) body libovoně zvolené trojice přímek v obecné poloze, potom každá další přímka protíná \(Z\) v alespoň dvou bodech – kdyby byl bod jen jeden, nebyly by tyto tři přímky v obecné poloze (to znamená, že se po dvou protínají ve třech různých bodech).

  Každá dvojice ze \(Z\) může pokrýt nejvýše jednu přímku, tedy celé \(Z\) může pokrýt nejvýše \(\binom{|Z|}{2}\) přímek.

  Odtud \(\binom{|Z|}{2}\ge n^2+n+1\), což dává \(|Z|^2-|Z| \ge 2n^2+2n+2\Longrightarrow |Z|> \sqrt2 n\).

  Lepší dolní odhad získáme, pokud spočítáme, že každou z \(n^2+n+1\) přímek musíme pokrýt dvěma body a každý bod může pokrýt nejvýše \(n+1\) přímek.

  Odtud \(|Z|\ge \frac{2(n^2+n+1)}{n+1}> 2n\).

• Odpověď

  Pro velikost hledané množiny platí odhad \(2n < \min |Z| \leq 3n\).