Particiones que separan todos los subconjuntos

Question

Deje $A=\{1,2,\dots,n\}$ y deje $\mathcal{A}_1,\dots,\mathcal{A}_k$ ser particiones de $A$ en dos sets. Supongamos que para cada subconjunto $B\subseteq A$ de tamaño uniforme, no existe una partición de $\mathcal{A}_i$ tal que la mitad de los elementos de $B$ está en una parte de la partición y la otra mitad en la otra parte. ¿Cuál es el mínimo posible de $k$ para los que esto es posible?

Un asintótica obligado para $k$ ya sería lo suficientemente bueno. Por ejemplo, se puede utilizar sólo $k=O(n)$ particiones? O incluso algunos polinomio en $n$ particiones?

Si sólo se consideran los subconjuntos $B$ de tamaño dos, entonces podemos hacerlo con $\log n$ particiones por escrito a cada elemento de a $A$ en base dos y tienen $\mathcal{A}_i$ ser la partición de acuerdo a si el $i$th dígito es $0$ o $1$. Sin embargo, esto no funciona al $B$ es de tamaño arbitrario: Por ejemplo, entre los cuatro números de $001,010,011,111$, ninguno de los dígitos ha $0$ $1$ aparecen dos veces cada uno.

Answer 1

Yo bruta forzado con $n$, pasando de 2 a 8. El mínimo de $k$ $n$ se $1,2,2,3,3,4,4$. Me miré en el conjunto mínimo de particiones, y notaron que podían ser construidos como este:

1. Deje que el 1er juego de la 1ª partición de ser
   $\{\lfloor n/2\rfloor ,...,1\}$
2. Para obtener el 1er juego de la 2ª partición de cambiar el 1 de valor para el menor valor no utilizado $\{\lfloor n/2\rfloor+1 ,\lfloor n/2\rfloor-1,...,1\}$
3. Para obtener el 1er grupo de la 3ª partición cambiar la 2ª valor a la menor valor no utilizado
   $\{\lfloor n/2\rfloor+1 ,\lfloor n/2\rfloor+2,\lfloor n/2\rfloor-2,...,1\}$

y continuar hasta que el primer set de $\lfloor (n+1)/2\rfloor$ particiones. Los otros conjuntos debe ser complementa a la primera.

El uso de esta construcción continuó durante $n=9,...,22$, y se encontró que el $5,5,6,6,7,7,8,8,9,9,10,10,11,11$ particiones suficiente. Sin embargo, para estos $n$ I no de la fuerza bruta para confirmar minimality. Sé que esto no es una respuesta hasta que haya una prueba de la suficiencia de la $\lfloor (n+1)/2\rfloor$

Answer 2

Este es sub-óptima, pero da una primera obligado.

Deje $k_n$ ser la solución para $n$. Observe que $k_2=1$, dado por la sola partición $\{\{1\},\{2\}\}$, e $k_3=2$ por ejemplo $\{\{1,2\},\{3\}\}$$\{\{1\},\{2,3\}\}$. Supongamos que tenemos $k_{n'}$ todos los $n'\le n+1$, y que queremos encontrar $k_{n+2}$. Deje $B\subseteq[n+2]$, tratamos de construir un conjunto de particiones de resolver el problema.

• Si $B\subseteq[n]\subset[n+2]$, entonces podemos considerar simplemente las particiones de resolver el problema de $[n]$ y agregarlos $n+1$ $n+2$ en cualquier manera que nos gusta.
• Si $B$ contiene $n+1$$n+2$, entonces podemos tomar la partición $X\sqcup Y=[n]$ de la solución del problema de $n$, y considerar la posibilidad de $X':=X\cup\{n+1\}$$Y':=Y\cup\{n+2\}$.

Por lo tanto, estas posibilidades están cubiertos por considerar $k_n$ particiones. Además, si $B$ contiene $n+1$ pero no $n+2$ (o viceversa), entonces vamos a $m$ ser el mayor elemento de $B\cap[n]$. Deje $X\sqcup Y=[m-1]$ ser la solución para el problema de $m-1$ $B\cap[m-1]$ y considerar la posibilidad de $X':=X\cup\{m,...,n\}$$Y':=Y\cup\{n+1,n+2\}$. A continuación, $X'\cup Y'=[n+2]$ resuelve el problema. Esto demuestra que $$k_{n+2}\le\sum_{i=0}^nk_n\ ,$$ que es bastante, obviamente, limitada por la secuencia de Fibonacci con $F_0=F_1=1$, $$k_n\le F_{n-1},\qquad n\ge2\ .$$ Así tenemos por ejemplo $$k_4\le3,\qquad k_5\le5,\qquad k_6\le8\ ,$$ y así sucesivamente.

---

Observe que en realidad tenemos $k_4=2$, teniendo $$\{\{1,3,\},\{2,4\}\},\{\{1,2\},\{3,4\}\}\ ,$$ ya están demostrando que el obligado no son óptimas.