No es una respuesta completa (o tal vez: responder a una pregunta diferente)
Discusión: Para abreviar, escriba $U = |\bigcup S_i|$ . Dejemos que $f(k,p)$ denotan el mínimo $U$ en función de $k$ (entero) y $p$ (número entero par). No hay descomposición $f(k,p) = g(k) \cdot p$ que se mantiene exactamente para todos los $k,p$ . (Por ejemplo, si $p=2, k=5$ la única solución que se me ocurre tiene $U = 6$ donde cada conjunto tiene 1 elemento único para sí mismo y 1 elemento común a todos los conjuntos, por lo que $g(5) = 6/2=3$ . Mientras tanto, el OP mostró un ejemplo para $p=6, k=5, U=10$ así que $g(5) = 10/6 = 5/3$ .) Por esa razón, también me parece extraño decir que "asumamos" $p$ es grande y altamente compuesto... a menos que lo que realmente le interesa es minimizar la proporción $U/p$ por ejemplo, para grandes $p$ o para una óptima $p$ . Por ejemplo, ¿le interesaba tal vez $h(k) = \min_p {f(k,p) \over p}$ es decir, la relación mínima (que se mantiene para algunos $p$ es decir, minimizado sobre todos los enteros pares posibles $p$ )?
De todos modos, dependiendo de si quieres minimizar el tamaño del universo $U$ o minimizar la relación $U/p$ Las respuestas pueden ser diferentes. El resto de este post muestra 2 familias distintas de soluciones, una mejor para minimizar $U$ y el otro mejor para minimizar $U/p$ .
Familia 1: basada en $d$ -vectores binarios de bits
Considere $d$ -vectores binarios de bits $v \in \{0,1\}^d$ . Sea $D=\{1, 2, ..., d\}$ denotan las posiciones de los bits. Sea $T$ sea un subconjunto no vacío de $D$ . Hay $2^d - 1$ tales subconjuntos, que denominamos $T_1, T_2, ..., T_{2^d -1}$ .
-
Definir $S_i = \{v \in \{0,1\}^d: \sum_{t \in T_i} v_t = 1 \pmod 2\}$ . Es decir, para cualquier vector $v$ , sumar (módulo 2) todos los bits $v_t$ en las posiciones $t \in T_i$ y si la suma es $1$ entonces el vector pertenece a $S_i$ Si no, no lo hace. Por ejemplo, para $T_i = \{2,3,5\}$ cualquier vector $(*,1,1,*,1,*,*) \in S_i$ pero cualquier vector $(*,1,0,*,1,*,*) \notin S_i$ , donde $*$ denota un comodín ( $0$ o $1$ ).
-
Para cualquier $i$ es obvio que exactamente 1/2 de todos los vectores están en $S_i$ es decir $|S_i| = 2^{d-1} = p$ .
-
Creo que también es cierto (aunque no se me ocurre una prueba breve) que para cualquier $i, j$ exactamente 1/4 de todos los vectores están en $S_i \cap S_j$ es decir $|S_i \cap S_j| = 2^{d-2} = p/2$ .
Así, los conjuntos $S_i$ cumplen los requisitos del PO. Hay $2^d - 1$ tales conjuntos, y por supuesto no es necesario utilizarlos todos. En otras palabras, hemos construido ejemplos, parametrizados por $d$ , donde:
- tamaño del juego individual $p = 2^{d-1}$
- número de juegos $k \le 2^d - 1$
- tamaño del universo $U = 2^d - 1$ porque todos los vectores están en la unión EXCEPTO el vector cero
- relación $U/p = {2^d - 1 \over 2^{d-1}}$ La fórmula original sugerida por el PO es la misma.
Familia 2: basada en $m$ -elija- $n$
Permítanme exponer ahora una familia diferente de soluciones que generalizan la del PO $k=5, p=6$ ejemplo.
Suponga que tiene $m$ objetos distintos $\{1, 2, ..., m\}$ y tú eliges $n<m$ de ellos. Por supuesto, hay $L={m \choose n}$ formas de hacerlo, es decir, hay $L$ tal tamaño $n$ subconjuntos. Ordene estos $L$ subconjuntos lexicográficamente y llamarlos $T_1, T_2, ... T_L$ . Por ejemplo, si $n=3$ entonces $T_1 = \{1,2,3\}, T_2 = \{1,2,4\}, ..., T_L = \{m-2, m-1, m\}$ etc. Ahora forme lo siguiente $m\times L$ matriz $A$ :
- $A_{ij}=1$ si el objeto $i \in T_j$ .
- $A_{ij}=0$ de lo contrario.
Es decir, el $j$ columna de $A$ es el vector booleano de pertenencia a $T_j$ . Ahora cambia tu perspectiva y...
-
Identificar el filas de $A$ como el de la OP $S_i$ conjuntos.
-
Identificar el conjunto de columnas como el universo $\bigcup S_i$ y en particular, $L = |\bigcup S_i| = U$ .
Las siguientes afirmaciones son válidas:
-
Cada fila contiene el mismo número de $1$ s: efectivamente, $\forall i, \sum_j A_{ij} = {m-1 \choose n-1}$ independientemente de $i$ . Este es el número de subconjuntos $T_j$ que contiene $i$ que es igual al número de formas de elegir el resto $n-1$ de los elementos restantes $m-1$ posibilidades. Como identificamos cada fila $i$ como el conjunto del OP $S_i$ Esto significa que $|S_i| = p = {m-1 \choose n-1}$ .
-
Para dos filas cualesquiera $i, i'$ su intersección contiene el mismo número de $1$ s: efectivamente, $\forall i, i', \sum_j (A_{ij}A_{i'j}) = {m-2 \choose n-2}$ independientemente de $i, i'$ . Este es el número de subconjuntos $T_j$ que contiene tanto $i$ y $i'$ que es igual al número de formas de elegir el resto $n-2$ de los elementos restantes $m-2$ posibilidades. Dado que identificamos las filas $i, i'$ como los conjuntos del OP $S_i, S_{i'}$ Esto significa que $|S_i \cap S_{i'}| = p/2 = {m-2 \choose n-2}$ .
-
Ahora resolvemos: ${m-2 \choose n-2} = {1 \over 2} {m-1 \choose n-1} \implies n = 1 + {m-1 \over 2} = {m+1 \over 2}$ .
Es decir, parametrizado por el entero impar $m$ podemos definir $n = {m+1 \over 2}$ y hemos expuesto una colección de conjuntos (filas de $A$ ) donde:
- tamaño del juego individual $p={m-1 \choose n-1}$
- número de juegos $k \le m$
- tamaño del universo $U = L = {m \choose n}$ el número de columnas de $A$
- relación $U/p = {m \choose n} / {m-1 \choose n-1} = m/n = {2m \over m+1}$
Ejemplos y comparaciones:
La siguiente tabla muestra, para varias opciones de $k$ Los "mejores" ejemplos ofrecidos por cada familia y el resultante $p, U, U/p$ . (En cada familia, el mejor se obtiene tomando el menor $d$ o $m$ posible).
Family 1 Family 2
-------- --------
k d p U U/p m n p U U/p
--- --------------- -------------------
3 2 2 3 3/2 3 2 2 3 3/2
4,5 3 4 7 7/4 5 3 6 10 5/3
6,7 3 4 7 7/4 7 4 20 35 7/4
8,9 4 8 15 15/8 9 5 70 126 9/5
10,11 4 8 15 15/8 11 6 252 462 11/6
12,13 4 8 15 15/8 13 7 . . 13/7
14,15 4 8 15 15/8 15 8 . . 15/8
Como puede observarse, la familia 1 suele tener un tamaño mucho menor $U$ (excepto la igualdad cuando $k=3$ ), pero la familia 2 tiene un tamaño menor $U/p$ (excepto la igualdad cuando $k=3, 6,7, 14, 15$ Y si puedo extrapolar: $k= 30, 31, 62, 63,$ etc)
