Sea $X$ un conjunto con $n$ elementos y $S_1$, $S_2$, $\ldots$, $S_m$ subconjuntos de $X$, cada uno con $3$ elementos y tales que la intersección de cualesquiera dos tiene a lo más un elemento.
Muestra que existe un subconjunto $S$ de $X$ con al menos $\lfloor \sqrt{2n} \rfloor$ elementos tal que no contiene a ningún $S_i$ para $i=1,2,\ldots,m$.
martes, 7 de febrero de 2012
Suscribirse a:
Comentarios de la entrada (Atom)
2 comentarios:
Decimos que $L\subset X$ es bueno si $L$ no contiene a ningún $s_i$.
Sea $T=\{t_1,t_2...t_k\}$ el máximo conjunto bueno y $R=\{r_1,r_2...r_{n-k}\}$ el complemento de $T$ en $X$. Ahora veamos que $|T|\leq \sqrt{2n} -1}$ nos lleva a una contradicción. Como $T$ es máximo, para todo $r_i\in R$ existe un $s_j$ tal que $|T\cap s_j|=2$, porque si $s_j$ no existiera entonce podríamos "meter" a $r_i$ en $T$ y este seguiría siendo bueno, lo cual contradeciría su maximilidad. Ahora consideremos las ternas de la forma $Q_i=(r_i, s_j, (t_k,t_l))$ donde $r_i\in R$, $r_i\in s_j$ y $s_j\cap T =(t_k,t_l)$, es claro entonces por definción que si dos de estas ternas tienen entradas en los $r_j$ distintas entonces tienen la entrada en los $s_j$ distinta, ahora, como $|R|\leq n-\sqrt{2n}+1$ por ser $R$ el complemento de $T$ entonces hay al menos $n-\sqrt{2n}+1$ de estas ternas, y como $|T|\leq \sqrt{2n}-1$ entonces $T$ tiene a lo más $n-\frac{3}{2}\sqrt{2n}+1$ parejas de la forma $(t_l,t_k)$ entonces por casillas hay dos ternas distintas $Q_a, Q_b$ con la misma entrada en $(t_l,t_k)$ y como son distintas con distinta entrada en las $s_j$ lo cual significa que hay dos conjuntos $s_a$, $s_b$ que se intersectan en una pareja en $T$ lo cual contradice la hipótesis de que los $s_j$ se intersectan a lo más en uno.
Publicar un comentario