$n$ -subconjuntos de elementos del conjunto $\{1,2, ..., 2n\}$ .

Question

Hay $\binom{2n} {n}$ , $n$ -subconjuntos de elementos del conjunto $\{1,2, ..., 2n\}$ . Estoy estudiando la cuestión de si se puede elegir entre estos subconjuntos $\frac12\binom{2n} {n}$ subconjuntos tales que:

i) cada elemento de $1$ a $2n$ pertenece exactamente a $\frac14 \cdot\binom{2n} {n}$ de los subconjuntos seleccionados;

ii) dos subconjuntos cualesquiera seleccionados tenían al menos un elemento común.

Si $n$ es una potencia de dos, entonces la respuesta es no, porque entonces $\binom{2n} {n}$ no es divisible por $4$ .

Si $n$ no es una potencia de dos, entonces $\binom{2n} {n}$ es divisible por $4$ . Para $n = 3$ He encontrado un ejemplo:

$$\{1,2,3\},\{1,2,4\},\{1,3,5\},\{1,4,6\},\{1,5,6\}$$ $$\{2,3,6\},\{2,4,5\},\{2,5,6\},\{3,4,5\},\{3,4,6\}$$

No sé cuál es la respuesta para otros $n$ por ejemplo, cuando $n = 9$ .

El control informático es demasiado grande.

Answer 1

Este es un método para cuando $2n-1$ es primo, y $2n\choose n$ es un múltiplo de 4.
Dejemos que $M=\{1,2,\ldots,2n-1\}$ .
Dejemos que $B$ sea la colección de $(n-1)$ -subconjuntos de elementos de $M$ .
$C$ será un subconjunto de la mitad de los conjuntos de $B$ de la siguiente manera:
Comienza con $C$ vacía. Elige cualquier $b\in B$ que no ha sido elegido. Póngalo en $C$ junto con sus desplazamientos $b_i=\{g+i\pmod{2n-1}:g\in b\}$ . Por ejemplo, si $2n-1=11$ y $b=\{1,2,4,6,7\}$ , entonces también se incluye en $C$ :
$$\{2,3,5,7,8\},\{3,4,6,8,9\},\{4,5,7,9,10\},\{5,6,8,10,11\},\{6,7,9,11,1\},\{7,8,10,1,2\},\{8,9,11,2,3\},\{9,10,1,3,4\},\{10,11,2,4,5\},\{11,1,3,5,6\}$$ Así que ponte $2n-1$ conjuntos a la vez en $C$ . Sigue añadiendo conjuntos de $B$ en $C$ hasta que tengas exactamente la mitad. Cada número de $1$ a $2n-1$ aparece en el mismo número de conjuntos en $C$ . Más adelante incluiremos $2n$ en cada uno de estos conjuntos.
Dejemos que $D$ sea la colección de $n$ -subconjuntos de elementos de $M$ , ninguno de los cuales es el complemento de un $c\in C$ . Cada número de $1$ a $2n-1$ también aparece en el mismo número de elementos de $D$ .

Su juego es $\{c\cup\{2n\}:c\in C\}\cup D$

Todos los números de $1$ a $2n-1$ aparecen igualmente en $C$ y en $D$ . $2n$ aparece en la mitad de los conjuntos; así que todos aparecen exactamente en la mitad de los conjuntos.
Si dos conjuntos provienen del $C$ lado, tienen $2n$ en común.
Si dos conjuntos provienen del $D$ lado, tienen $2n$ elementos de los números en $M$ por lo que algún elemento está en ambos conjuntos.
Si un conjunto proviene de $C$ y uno de $D$ Recuerde que $C$ y $D$ fueron elegidos para que $c\cup d\neq M$ por lo que tienen un elemento en común.