Juegos $S_i$ tal que $|S_i\cap S_j|\geq4$

Question

Que $A=\{1,2,\ldots,1600\}$ y $S_1,S_2,\ldots,S_{16000}$ sea subconjuntos de $A$ tal que $|S_i|=80$ % todos $i$. Muestran que alrededor del $i\neq j$, tenemos $|S_i\cap S_j|\geq4$.

Quiero Supongamos por contradicción que $|S_i\cap S_j|<4$ % todos $i\neq j$. Entonces tal vez el % de sistemas #% de #% deban ser demasiado "extendió" por lo que es imposible construirlas cuando tenemos sólo $S_i$ elementos. Pero no sé cómo capturar el "que se separa hacia fuera".

Answer 1

Deje $n=80$, por lo que tenemos $200n$ subconjuntos $S_i$ $n$ elementos cada uno, de un conjunto de $X$ $20n$ elementos. Han $a_k$ $($$0 \le k \le 200n$$)$ ser el número de elementos contenidos en exactamente $k$ subconjuntos. Entonces $$\mathcal{S}_0 = \sum_{k=0}^{200n} a_k = 20n$$ and $$\mathcal{S}_1 = \sum_{k=0}^{200n} ka_k = \sum_{1 \le i \le 200n} |S_i| = 200n^2.$$ Moreover, $$\mathcal{S}_2 = \sum_{k=0}^{200n} {{k(k-1)}\over2}a_k = \sum_{1 \le i < j \le 200n} |S_i \cap S_j|.$$

Así que para algunos $0 \le m \le 200n-1$ podemos resolver el sistema $$a + bm = {{m(m-1)}\over2}, \text{ }a + b(m+1) = {{m(m+1)}\over2},$$ leading to $a = -{{m(m+1)}\over2}$, $b = m$. Then $$a + bk = -{{m(m+1)}\over2} + km \le {{k(k-1)}\over2}$$ for all $0 \le k \le 200n$, because equivalent to $(k-m)(k-(m+1)) \ge 0$ $($and with equality for $k \in \{m, m+1\}$$)$. Por lo tanto $$a\mathcal{S}_0 + b\mathcal{S}_1 \le \mathcal{S}_2.$$

Considere ahora la expresión $N = a(20n) + b(200n^2)$, lo que queremos es maximizar. Tenemos $$N = -{{m(m+1)}\over2}(20n) + m(200n^2) = 10nm(20n - (m+1)) \le 100n^2(10n - 1)$$ $($with equality for $m \in \{10n-1, 10n\}$$)$.

Por otro lado, $\mathcal{S}_2$ $100n(200n-1)$ condiciones, por lo que uno de ellos es, al menos,$$\left\lceil\frac{100n^2(10n-1)}{100n(200n-1)}\right\rceil = \left\lceil\frac{n(10n-1)}{200n-1}\right\rceil\geq \left\lceil\frac{10n^2-n}{200n}\right\rceil$$ $$= \left\lceil\frac{n}{20}-\frac{1}{200}\right\rceil = \left\lceil 4-\frac{1}{200}\right\rceil = 4.$$

Answer 2

Ofreceré una sugerencia a través de un lema.

Lema: deja que $X$ ser una variable aleatoria. Entonces existe algún punto en el espacio de probabilidad donde $X \ge E[X]$ y también algún punto en el espacio de probabilidad donde $X \le E[X]$.