Combinatoria
Olimpiada Nacional de Irán (3ra Ronda) (2006)
Olimpiada Nacional de Irán (3ra Ronda) 2006 Problema 5
Sea $E$ una familia de subconjuntos de $\{1,2,\ldots,n\}$ con la propiedad de que para cada $A\subset \{1,2,\ldots,n\}$ existe $B\in F$ tal que $\frac{n-d}2\leq |A \bigtriangleup B| \leq \frac{n+d}2$ . (donde $A \bigtriangleup B = (A\setminus B) \cup (B\setminus A)$ es la diferencia simétrica). Denotemos por $f(n,d)$ la cardinalidad mínima de tal familia. a) Pruebe que si $n$ es par entonces $f(n,0)\leq n$ . b) Pruebe que si $n-d$ es par entonces $f(n,d)\leq \lceil \frac n{d+1}\rceil$ . c) Pruebe que si $n$ es par entonces $f(n,0) = n$
Inicia sesión para agregar soluciones y pistas