Determinar el mayor número natural $r$ con la propiedad de que entre cinco subconjuntos cualesquiera con $500$ elementos del conjunto $\{1,2,\ldots,1000\}$

Question

Pregunta:

Determinar el mayor número natural $r$ con la propiedad de que entre cinco subconjuntos cualesquiera con $500$ elementos del conjunto $\{1,2,\ldots,1000\}$ existen dos de ellas que comparten al menos $r$ elementos.

Por Ahora, afirmo que $\color{red}{ r \le 200} $ **

Las razones fueron las siguientes

Para todos $ k \in \{1, 2, \dots, 10\} $ deje $\color{red}{ A_k = \{100k - 99, 100k - 98, \dots, 100k\}}. $ Entonces, si nos fijamos en los subconjuntos $ A_1 \cup A_5 \cup A_6 \cup A_7 \cup A_9 $ y $ A_1 \cup A_2 \cup A_7 \cup A_8 \cup A_{10} $ y $ A_2 \cup A_3 \cup A_6 \cup A_8 \cup A_{9} $ y $ A_3 \cup A_4 \cup A_7 \cup A_9 \cup A_{10} $ y $ A_4 \cup A_5 \cup A_6 \cup A_8 \cup A_{10} $ vemos que dos de estos subconjuntos comparten exactamente $ 200 $ lo que implica que $\color{blue}{ r \le 200. }$

Conjeturo $\color{red}{r_{\max}=200?}$ y no puedo probarlo. Gracias.

Answer 1

Tiene usted razón. En realidad se trata de una pregunta sobre la teoría de la codificación. Llame a su familia de conjuntos $\mathcal{C}$ y a cada conjunto $A\in \mathcal{C}$ en su familia asocia un vector indicador en $1_A\in\{0,1\}^{1000}$ . Entonces se cumple la condición de que para cualquier $A,B\in \mathcal{C}$ que $A\cap B\ge r$ se convierte en $$d_H(1_A,1_B)=\Delta(A,B)= |A\cup B|-|A\cap B|=|A|+|B|-2|A\cap B|\le 1000-2r$$ donde $d_H$ denota la distancia de Hamming, y $\Delta$ denota unión disjunta. En otras palabras, buscamos un código de peso constante 500, longitud de bloque $n=1000$ y distancia $d=1000-2r$ .

El límite de Plotkin dice que si $d\ge 500$ entonces tenemos que $|\mathcal{C}|\le \frac{2d}{2d-n}$ . Enchufar $r=200$ obtenemos $d=600$ y, por lo tanto $|\mathcal{C}|\le \frac{1200}{200}=6$ . Obsérvese ahora que introducir el vector de todos los 0 en nuestro código (equivalentemente, el conjunto vacío en nuestra familia de conjuntos) no reduce la distancia, ya que todas las demás palabras de código tienen un peso de 500. Por lo tanto, nos encontramos con que, de hecho, nuestra familia de conjuntos tiene un tamaño máximo de 5. Si aumentamos $r$ en absoluto, entonces el límite de Plotkin se hace más estricto y el tamaño de nuestra familia de conjuntos se reduce a 4 como máximo.

Answer 2

Observe que $|A \cap B| \geq 200$ es equivalente a $A \Delta B \leq 600$ aquí, donde $A \Delta B=(A \setminus B) \cup (B \setminus A)$ .

Considere la suma $S=\sum_{1 \leq i<j\leq 5}A_i \Delta A_j$ . Cada uno de los 1000 elementos puede contribuir como máximo a 6 de los 10 términos (el máximo se alcanza cuando un elemento está presente exactamente en 2 de los 5 conjuntos o exactamente en 3 de los 5 conjuntos). Así pues, $S \leq 6000$ y por lo tanto una de estas diferencias simétricas debe ser como máximo 600.

Answer 3

Creo que puede estar en lo cierto. Dejaré que otros juzguen la solidez de mi razonamiento.

Sea $a_n$ sea el número de elementos que aparecen en $n$ conjuntos. Así que tenemos

$$a_1+a_2+a_3+a_4+a_5=1000$$ $$a_1+2a_2+3a_3+4a_4+5a_5=2500$$

Restando, obtenemos

$$a_2+2a_3+3a_4+4a_5=1500$$

Consideremos ahora un grafo con 5 vértices, cada uno de los cuales corresponde a uno de nuestros subconjuntos. Cada arista del grafo tiene un peso igual al número de elementos que comparten los dos subconjuntos. La suma de los pesos de las $10$ bordes es

$$a_2+3a_3+6a_4+10a_5$$

Parece razonable que la forma de minimizar este valor sea hacer que $a_2$ lo más grande posible. La mejor solución parece ser $500$ que aparecen dos veces y $500$ aparece $3$ veces. Esto hace que la suma de los pesos sea igual $500+3(500)=2000$ . Dividiendo esto a partes iguales entre cada arista se obtiene $10$ aristas con un peso de $200$ cada uno.

Answer 4

Toma arbitraria $5$ subconjuntos $A_1,A_2,A_3,A_4,A_5$ cada una con cardinalidad de $500$ . Diga $d_k$ es el número del conjunto que contiene el número $k$ . Entonces tenemos $$ \sum_{i=1}^{1000}d_i = \sum _{i=1}^5|A_i| =2500$$

Conectar un par de conjuntos con el número $k$ si $k$ está en su intersección y $a_{i,j} = |A_i\cap A_j|$ . Supongamos que $m= \max\{a_{i,j};i\ne j\}$ . Entonces tenemos: $${5\choose 2}m\geq \sum a_{i,j} = \sum _{i=1}^{1000}{d_i\choose 2} \geq 500{3\choose 2}+ 500{2\choose 2} $$ de aquí obtenemos $m\geq 200$ .