Rompecabezas matemático: dividir un conjunto en dos conjuntos separados

Question

Le $X$ ser el conjunto de todos los que no vacía de subconjuntos de a $\{a,b,c,d,e,f\}$. Por lo $X=\{a,b,c,d,e,f,ab,ac,ad,ae,af,bc,bd,be,bf,cd,ce,cf,de,df,ef,abc,\cdots,abcdef\}$; es decir, $|X|=63$. Queremos partición $X$ en dos conjuntos disjuntos $Y$ $Z$ tal forma que: (i) $|Y|=13$; (ii) Dado cualquier elemento $z \in Z$, $\exists ~ y_1,y_2 \in Y$ tal que $y_1y_2=z$; (iii) Si $x_1,x_2 \in Y$,$x_1x_2 \notin Y$.

Nota los siguientes:

(1.) $(X,\cdot)$ es conmutativa: Dado $ x=ab,y=cd\in X$,$x \cdot y=(ab)(cd)=abcd=adbc=dcba=\cdots=cdab=y \cdot x$;

(2.) Dos cartas mismo se cancela a sí mismos: $(ab)(ac)=aabc=bc$.

Mi objetivo es encontrar a $Y$. He intentado muchas cosas en vano. Por ejemplo, $Y$ no puede contener todas las palabras de longitudes $1$, $5$ y $6$ ya que este no puede dar todas las palabras de longitud $3$ o $4$.

Cualquier ayuda en la solución de $Y$ será altamente apreciada.

Answer 1

Así que creo que esto va a funcionar:

$$ Y = \{a, b, c, d, e, f, abce, bcdf, acde, bdef, acef, abdf, abcdef\} $$

Es decir, $Y$ se compone de toda una carta de conjuntos, la cuatro-letra de set $abce$ y su "rotaciones", y la de seis letras que establezca $abcdef$. Que no $y_1, y_2 \in Y$ admiten $y_1 \cdot y_2 \in Y$ puede ser visto de la siguiente manera:

• Una carta de conjunto combinado con una carta de conjunto produce una de dos letras o el conjunto vacío.

• Una carta de conjunto combinado con un cuatro-letra de conjunto produce una de tres letras o cinco letras de conjunto.

• Una carta de conjunto combinado con las seis letras de conjunto produce un cinco letras de conjunto.

• Una de la cuatro-letra de set combinado con las seis letras de conjunto produce de dos letras de conjunto.

• Las seis letras de conjunto combinado con sí mismo produce el conjunto vacío.

Ninguno de estos productos puede ser en $Y$. Que sale de la combinación de dos de las cuatro letras de conjunto. Considere la posibilidad de $abcd$. Combinado con sí mismo, produce el conjunto vacío. Combinado con $acde$ o $acef$, se produce de dos letras de conjunto. Finalmente, combinado con $bcdf, bdef, abdf$, respectivamente, se produce la $adef, acdf, cdef$. Ninguno de esos es en $Y$.

Que todos los $z \in Z = X \backslash Y$ puede ser producido como $z = y_1 \cdot y_2$,$y_1, y_2 \in Y$, puede ser visto de la siguiente manera:

• El conjunto vacío y el todo de una sola letra conjuntos no están en $Z$.

• Todos los dos de la carta establece que puede ser producido por la combinación de las letras individuales de $Y$.

• La tres-letra de set $abc$ puede ser producido como $abce \cdot e$. Todas las "rotaciones" de $abc$ puede ser producida por la rotación de los elementos de la $Y$.

• La tres-letra de set $abd$ puede ser producido como $abdf \cdot f$. Todos los de su "rotaciones" puede ser producido de manera similar.

• La tres-letra de set $abe$ puede ser producido como $abce \cdot c$. Todos los de su "rotaciones" puede ser producido de manera similar.

• La tres-letra de set $ace$ puede ser producido como $abce \cdot b$. Su rotación, $bdf$, se puede producir de manera similar. No hay otros tres-letra de conjuntos.

• Todos los cinco de la carta establece que puede ser producido por una combinación de las seis letras que establezca $abcdef$ según la letra que falta.

• Hay, por supuesto, ninguna de las seis de la carta establece en $Z$.

Que deja, de nuevo, la cuatro-letra de conjuntos no en $Y$. $Y$ ya contiene todos los de la cuatro-letra de conjuntos donde las letras que faltan son $ac$, o su "rotaciones". Los otros cuatro-letra de conjuntos puede ser producido de la siguiente manera:

• La cuatro-letra de set $abcd$ puede ser producido como $bdef \cdot acef$. Todos los de su "rotaciones" puede ser producido de manera similar.

• La cuatro-letra de set $abde$ puede ser producido como $bcdf \cdot acef$. Todos los de su "rotaciones" puede ser producido de manera similar. No hay otros cuatro-letra de conjuntos.

---

La motivación detrás de este set de construcción fue algo como esto: sería conveniente Que todos los conjuntos en $Y$ de un determinado "longitud" fueron las rotaciones de cada uno de los otros, para, a continuación, la construcción de los otros juegos podrían ser fácilmente demostrado.

A lo largo para hacer los sets? A pesar de que las normas que permitieron que para algunos "superposición" (que es, algunos $z$ sería producido a través de dos o más combinaciones), la condición de que $|Y| = 13$ no deja mucho espacio para los residuos, desde la $(13)(12)/2 = 78$ no es mucho mayor que $|Z| = 50$.

Se me ocurrió que la inclusión de todos de una sola letra establece produciría todos de dos letras que se establece en la negociación. La introducción de la cuatro-letra establece tenía la ventaja de que una carta de conjuntos y de la cuatro-letra de conjuntos no se pueden combinar para producir ellos mismos. Dejó a un único conjunto restante, y la opción obvia era el único de seis letras que establezca $abcdef$.

Entonces la única pregunta restante fue que cuatro letras de los conjuntos contienen. Yo primero consideró $abcd$, pero que dejó una brecha de dos espacios ($ef$), y ninguna combinación podría producir, por ejemplo, $ace$, el cual carece de cualquier brecha de ese tamaño. La siguiente conjetura es $abce$, y que funciona.

Answer 2

Se ha señalado en los comentarios que el problema es equivalente a la siguiente: encontrar un subconjunto $Y$ del espacio vectorial $V=\mathbb{F}_2^6$ tal que $|Y|=13$, e $Y\oplus Y=V\setminus Y$.

Necesariamente, los elementos de $Y$ deben ser linealmente independientes (de lo contrario sólo se podía conseguir a $32$ combinaciones lineales, mucho menos $50$ sumas de dinero.) Las condiciones en las $Y$ son invariantes bajo invertible, transformaciones lineales, por lo que podemos suponer sin pérdida de generalidad que la densidad de uno de los vectores (es decir, singleton subconjuntos) en $Y$.

Por lo tanto, todos de la densidad de dos vectores debe ser en $V\setminus Y$. Ponemos dos complementarios de la densidad de tres vectores en $Y$ -, podemos asumir que estas son las $(1,1,1,0,0,0)$$(0,0,0,1,1,1)$ --$(1,1,1,1,1,1)\in Y\oplus Y$. Esto nos deja $5$ vectores para elegir con el fin de obtener todos los vectores de la densidad $3$, $4$ y $5$. Desde el singleton son en $Y$, recogemos todos los $5$ restante de los vectores que tienen la densidad de $4$, de tal manera que (a) cada densidad-$5$ vector que contiene a uno de ellos (es decir, la densidad de $4$ vectores tomados en conjunto tiene un cero en cada posición), y (b) cada densidad-$3$ vector está contenida en uno de la densidad-$4$ vectores. Esto es fácil de hacer; una solución es: $${a, b, c, d, e, f, b, c, d, e, f, b, c, d, f, c, d e, a b d f a c e f, a c d f}$$

Por cierto, para $n=7$ letras, hay una solución con $|Y|=21$: $${a, b, c, d, e, f, g, c, e, a b c e f g c d f g, b, e, f, g, b, c, g, a e f g, d, f, b, c, d, f, b f, b, d, c d, e f, d, e, f, c, e, f, g, a b d f g}$$ Yo sospecho que es óptimo.