5 votos

Problema combinatorio: la construcción de ciertos subconjuntos de un conjunto de tamaño de ocho.

Me gustaría encontrar a ocho subconjuntos $S_1$, $S_2$,$\ldots$,$S_8$ de $\{1,2,3,\ldots,8\}$ con las siguientes propiedades:

1) Cada una de las $S_i$ tiene tamaño 3, y cada $i$, $1\leq i\leq 8$, es precisamente en tres de las $S_i$.

2) El $S_i$ tiene un único "sistema de los distintos representantes". Es decir, sólo hay una manera de elegir los elementos de $x_i\in S_i$ todos los $x_i$ distintos, o, equivalentemente, que el $\{x_1,x_2,\ldots,x_8\}=\{1,2,3,\ldots,8\}$.

No sé si tales subconjuntos que debe de existir. He intentado a partir de $S_i=\{i,i +1,i+2\}$ (modulo 8), so e.g. $S_5=\{5,6,7\}$ and $S_8=\{8,1,2\}$; esto satisface (1) y, a continuación, traté de cachondeo cambio de un par de elementos a obtener (2) a trabajar, pero yo no. Hay un campo finito de tamaño 8, pero yo no podía ver un natural camino de la construcción de ocho subconjuntos de tamaño 3 que iba a funcionar. Del mismo modo hay una campo finito de tamaño 9, pero yo no podía ver una forma natural de construir ocho subconjuntos de su grupo multiplicativo de tamaño 3 que iba a funcionar. Este tipo de cosas es un largo camino de mi zona y yo que pensaba que debo hacer en caso de que me había perdido de algo.

26voto

Martin Puntos 178

Si Wikipedia la entrada de la Sala del Matrimonio Teorema de aquí es que se cree, esto no es posible. Asunción (1) implica que el $S_i$ satisfacer Hall del Matrimonio Condición, así que por Marshall Hall de la variante de la Sala del Matrimonio Teorema siempre hay al menos seis de los sistemas de los distintos representantes.

0voto

bentsai Puntos 1886

El argumento en los comentarios de la aceptó respuesta es defectuoso. Consideremos el conjunto del sistema: $$\big(123,123,123,124,125,126,127,128\big).$$ It has the SDR $(1,2,3,4,5,6,7,8)$. If we delete it, we obtain: $$\big(23,13,12,12,12,12,12,12\big)$$ which doesn't have an SDR. The problem is that Marshall Hall Jr's extension to Latin rectangles doesn't apply here; the column sets of Latin rectangles have stronger assumptions than those imposed on the sets $S_i$. However, his lower bound $3!$ todavía se aplica (Wikipedia ref.).

Esta pregunta equivale a preguntar si hay un $8 \times 8$ $(0,1)$-matriz con exactamente tres $1$'s en cada fila con permanente $1$. Sabemos que no es posible, por la $3!$ límite inferior. El ejemplo anterior corresponde a la matriz: $$\left(\begin{array}{cccccccc} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array}\right)$$ que ha permanentes $3!$. Así que el mínimo es alcanzado por este ejemplo.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X