Separar$2n$ elementos con subconjuntos de tamaño$n$

Question

Supongamos que tengo un set $X$ $2n$ elementos ($n$ número natural distinto de cero). Ahora quiero encontrar una colección de subconjuntos de a $X_1, \ldots, X_k$ $X$ tal que

• Cada $X_i$ contiene $n$ elementos.
• Para cada $x, y \in X$, existe un $X_i$ tal que $x \in X_i$ $y \not\in X_i$ o $x \not\in X_i$ $y \in X_i$ ($X_i$ "separado de" los elementos de $X$, en que la topología en $X$ generado por el $X_i$ es la prueba de Kolmogorov)
• $k$ es mínima con respecto a las anteriores propiedades.

Un algoritmo para encontrar $X_1, \ldots, X_k$ sería genial, pero yo soy su mayor parte buscando una forma para calcular el $k$. Mi intuición me dice que $k$ debe ser de al menos $\log_2(2n)$, más específicamente, me siento como $$\max_{x \in X} \# \lbrace y \X \mid \no\existe i \en \lbrace 1, \ldots, j \rbrace : x \in X_i \enspace \& \enspace y \no\en X_i \rbrace \geq \log_2(\frac{2n}{j})$$ para todos los $j \in \lbrace 1, \ldots, k \rbrace$, pero no sé cómo probar esto.

Answer 1

Supongamos $X$ contiene $2^l$ elementos. Deje $(A_i^m)$ ser parte de la familia de subconjuntos de a $X$ de los no separados de los elementos después de la introducción de $X_1, \cdots, X_m$, es decir, conjuntos de elementos para los que el segundo requisito no se sostiene (verificar que estos conjuntos están bien definidos y de forma única partición $X$). En definitiva, queremos que todos los subconjuntos de a $A_i$ contienen un solo elemento (es decir, cada elemento está separado de todos los demás elementos).

Con cada una de las $X_i$ queremos separar los tantos elementos como sea posible. Ahora, en la primera se $A_1 = X$ contiene $2^l$ elementos y tomamos $X_1$ simplemente un conjunto arbitrario de $n$ elementos. Después de esto, tenemos conjuntos de $A_1$, $A_2$, ambos contienen $2^{l-1}$ elementos. Ahora, con $X_2$ otra vez podemos dividir ambos en la mitad, resultando en cuatro 'resto' juegos de con $2^{l-2}$ elementos. Continuar de forma recursiva a ver que $k=l$. Por otra parte, es claro que después de la introducción de $m$ conjuntos, $\max_i \# A_i^m \geq 2^{l-m}$, por lo que nuestro resultado es, en efecto óptimo.

Por ejemplo, comience con $X = A_1^0 = \{1,2,3,4,5,6,7,8\}$. Introducir $X_1 = \{1,2,3,4\}$ conseguir $A_1^1 = \{1,2,3,4\}, A_2^1 = \{5,6,7,8\}$. Introducir $X_2 = \{1,2,5,6\}$ $X_3 = \{1,3,5,7\}$ al finalizar el trabajo. (Asegúrese de comprobar los conjuntos correspondientes a $(A_i^m)$.)

Ahora, cualquiera que sea el número de elementos de a $2n$, su 'divide' wil no ser óptima. Se puede comprobar que $\max_i \# A_i^m \geq 2n\cdot2^{-m}$ aún se mantiene.

Answer 2

No debería ser $k=\lceil log_2(2n) \rceil$ particiones, $2k$ conjuntos.

Tenemos las condiciones: $$\mathcal{P}_1:\forall X_i, \text{num}\{X_i\}=n$$ $$\mathcal{P}_2:\forall x_i,x_j \exists X_i, x_i \in X_i, x_j \not\in X_i$$

Es claro para los conjuntos de $2n=2^k$ elementos, las particiones son binarios, por lo tanto óptima. En virtud de este caso, la condición de $\mathcal{P}_2$ implica que el más fuerte: $$\mathcal{P}_{2b}:\forall x_i,x_j \exists X_i,X_j, x_i \in X_i, x_j \in X_j$$ porque cada partición requiere de su complemento. Si no hay complemento, la propiedad no se cumple. $$\forall X_i \exists Y_i=X -X_i$$

Si el conjunto contiene a $2n=2^k+2m$ elementos, $2m<2^k$, cada una de las $2m$ resto de los elementos deberá ser incluido en diferentes particiones disjuntas. De nuevo en este caso la partición complementar debe existir y la condición de $\mathcal{P}_{2}$ no introducir ningún beneficio en contra de $\mathcal{P}_{2b}$.