$S_1, \dots, S_6 \subseteq \{1,2,\dots,21\},$ demostrar que $|S_i \cap S_j| \ge 5$ o $|S_i^C \cap S_j^C| \ge 5$ para algunos $i,j.$

Question

Subconjuntos dados $S_1, \dots, S_6 \subseteq \{1,2,\dots,21\},$ Deseo probar $|S_i \cap S_j| \ge 5$ o $|S_i^C \cap S_j^C| \ge 5$ para algunos $i \ne j.$

Empecé asumiendo $|S_i^C \cap S_j^C| \le 4$ para todos $i \ne j.$ Esto nos da $|S_i \cup S_j| \ge 17$ para todos $i \ne j,$ y deseamos encontrar una intersección de tamaño $\ge 5.$ Probé el método probabilístico, el principio de encasillamiento y la prueba por contradicción, pero ninguna de estas técnicas funcionó.

Hasta ahora he conseguido que si el resultado no se cumple, tenemos $8 \le |S_i| \le 14$ para todos $i,$ pero no puedo descartar estos casos. También he intentado dibujar segmentos dentro de un $6 \times 21$ rectángulo para encontrar conjuntos que violaran la condición, y siempre fallaba cuando llegaba al $5$ de la fila, así que tal vez el límite no es tan agudo. El problema con el método probabilístico es que $p(k \in S_i \, \& \, k \in S_j) \ne p(k \in S_i)p(k \in S_j)$ ya que los eventos no son independientes. Si se utilizan las probabilidades condicionales para solucionar esto, se acaba obteniendo $\mathbb{E}(|S_i \cup S_j|) = \dots = \mathbb{E}(|S_i \cup S_j|).$ Este problema está fuera del ámbito de la combinatoria de herradura, por lo que dicha igualdad no es útil. El problema con el principio de encasillamiento es que, si bien le dará límites interesantes a los números dentro de $\{1,2,\dots,21\}$ apareciendo en al menos tal o cual cantidad de lances $S_i,$ no producirá un conjunto de números que aparezcan en dos conjuntos simultáneamente; podría estar sacando números diferentes una y otra vez.

¿Alguien tiene alguna pista o idea sobre cómo proceder? ¿Cuál sería la motivación de un enfoque exitoso?

Answer 1

Tomemos la configuración de la matriz de incidencia donde las filas corresponden a $S_i$ y las columnas corresponden a elementos $j$ . Ponga un 1 si $j \in S_i$ 0 en caso contrario.

Contamos los pares de columnas de ambos tipos $1-1$ y $0-0$ .
En cada columna, si hay $k$ de los mismos, entonces hay $ { k \choose 2 } + { 6-k \choose 2 } \geq 6 $ pares de columnas.
Así que hay al menos $ 21 \times 6 = 126 $ pares de columnas.

Hay $ { 6 \choose 2 } = 15 $ pares de filas, que contienen estos 126 pares de columnas.
Según el PP, al menos un par de filas contiene al menos $ \lceil \frac{126}{15} \rceil = 9 $ pares.
Por el PP, al menos $\lceil \frac{9}{2} \rceil = 5$ son del mismo tipo (ya sea $1-1$ o $0-0$ ).
Traduciendo hacia atrás, este par de subconjuntos contienen al menos 5 elementos en común ( $1-1$ ), o no lo hace ( $0-0$ ).

Answer 2

He encontrado una prueba. Las opciones de $S_1, \dots, S_6$ corresponden a colorear los cuadrados de un $6 \times 21$ rectángulo blanco o negro en función de si los elementos se encuentran en $S_i$ o no. Queremos encontrar $2$ filas y $5$ columnas tales que el $10$ Los cuadrados en las intersecciones de estas filas y columnas son todos del mismo color. Si una columna tiene $k$ cuadrados negros y $6-k$ pares blancos, contiene $\binom{6-k}{2} + \binom{k}{2} \ge 6$ pares monocromáticos. Hay $2$ colores y $\binom{6}{2} = 15$ posiciones para un par, por lo que hay $30$ combinaciones de posición-color para un par de columnas. Dado que $6 \cdot 21 > 30 \cdot 4,$ alguna combinación de color y posición aparece al menos $5$ veces como se desee.