Algoritmo de creación de subconjuntos con algunas propiedades

Question

Estoy tratando de para resolver el siguiente problema:

Vamos a decir, tenemos un conjunto de $A=\{1,2,3,...,49\}$.

Ahora, yo soy la definición de conjuntos de $A_1, A_2, A_3,...,A_n$ como seguir: $A_1=\{a_1,a_2,a_3,...,a_{30}\}$, $A_2= \{b_1,b_2,b_3,...b_{30}\}$, y así sucesivamente, donde todos los elementos de los conjuntos de $A_i$ son también elementos de $A$, lo que significa que son subconjuntos del conjunto de $A$. (Todos los conjuntos de $A_i$ ha $30$ elementos).

Ahora, estoy buscando un set$C=\{ A_1,A_2,A_3,...,A_n \}$, de modo, que si yo escojo al azar $6$ elementos de $A$, van a ser (al menos) en uno de los conjuntos de $A_i$.

¿Qué es $n$? Vamos a ver: lo primero de todo, ¿cuánto posibilidades son para recoger $6$ elementos de $A$? Hay $\binom{49}{6}=\large\frac{49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44}{6!}=13,983,816$

En segundo lugar, ¿cuánto de estas posibilidades que cubre uno de los conjuntos de $A_i$? Debido a que establezca $A_i$ $30$ elementos, cubre $\binom{30}{6}=\large\frac{30 \cdot 29 \cdot 28 \cdot 27 \cdot 26 \cdot 25}{6!}=593,775$

Ahora dividiendo ambos resultados, se da $23.55$ y esto significa, que necesitamos al menos $n=24$ (probablemente más, no estoy seguro).

Así que la pregunta es, ¿cómo encontrar el conjunto $C$?

Digamos, podemos empezar así: $A_1=\{1,2,3,...,30\}$, este será el primer set. Pero ¿qué es lo siguiente? Con algún algoritmo puedo implementarlo en C o Java, pero no sé cómo empezar. Gracias.

Answer 1

Un enfoque posible es partición $A$ en 10 grupos (decir $B_i$), cada uno de tamaño 5 (uno será de tamaño 4). Definir su $A_j$ como la Unión de cualquier 6% arriba $B_i$. Para obtener tal $\binom{10}{6}$ $A_j$ (algunos de ellos tendrán tamaño 29, pero usted puede lanzar en algún elemento aleatorio si desea hacerla 30). Cualquier conjunto de 6 elementos toca en la mayoría de los 6 bloques $B_i$ y por lo tanto, está presente en uno de lo anterior $A_j$. Esto da un límite superior para el tamaño de $C$ $\binom{10}{6} = 210$.