18.1: Sistemas triples Steiner y Kirkman

En\(1844\), W.S.B. Woolhouse, editor del Diario de Damas y Caballeros, planteó el problema de premios anuales de esa publicación:

Determinar el número de combinaciones que se pueden hacer de\(n\) símbolos,\(p\) símbolos en cada uno, con esta limitación, que ninguna combinación de\(q\) símbolos que pueda aparecer en alguno de ellos se repetirá en ninguna otra.

Si tomamos\(q = 2\) entonces este es esencialmente un diseño con\(k = p\) y\(v = n\), aunque no necesita ser equilibrado; algunos pares pueden aparecer una vez mientras que otros pares no aparecen. A pesar de que algunas respuestas fueron impresas en\(1845\), no fueron satisfactorias, y en\(1846\) por Woolhouse repitió la pregunta para el caso especial\(q = 2\) y\(p = 3\).

En\(1847\), El Rev. Thomas Kirkman (mencionado anteriormente en el Capítulo\(13\)) encontró una solución completa a este problema en el caso en que el diseño se equilibra (con\(λ = 1\)), e hizo algunos avances hacia la solución del problema completo. En nuestra terminología, su solución determinó completamente los valores\(v\) para los que\((v, 3, 1)\) existe un BIBD.

Aunque Steiner no estudió sistemas triples en\(1853\), se le ocurrió el resultado de Kirkman de forma independiente, y su trabajo se difundió más ampliamente en círculos matemáticos, por lo que estas estructuras aún llevan su nombre. A pesar de ello, como veremos en la siguiente sección, existe un problema relacionado que lleva el nombre de Kirkman.

Definición: Triple System

Un sistema triple es un diseño equilibrado (regular) en el que cada bloque tiene cardinalidad\(3\); es decir, un BIBD\((v, 3, λ)\).

Un sistema triple Steiner es un sistema triple con\(λ = 1\).

Ejemplo\(\PageIndex{1}\)

El BIBD cíclico\((19, 3, 1)\) dado en el Ejemplo 17.2.2 es un sistema triple Steiner. Así es el diseño en\(7\) puntos dado por

\[\{1, 2, 3\}, \{1, 4, 5\}, \{1, 6, 7\}, \{2, 4, 6\}, \{2, 5, 7\}, \{3, 4, 7\}, \{3, 5, 6\}\]

Notación

Dado que la única variable en un sistema triple Steiner es\(v\), para tal sistema en v puntos usamos la notación STS\((v)\).

Los sistemas triples pueden parecer un caso muy especial de diseños, y sería razonable preguntarse por qué hemos optado por destacarlos para un estudio y atención especiales. La respuesta es que los sistemas triples pueden considerarse como los ejemplos más pequeños e interesantes de diseños, ya que (como se señaló anteriormente) si no\(k = 1\) hay pares en ningún bloque y el diseño es trivial; y si\(k = 2\) entonces los bloques son simplemente copias de cada par posible del conjunto\(V\). Así que los sistemas triples son un punto de partida natural cuando estamos aprendiendo sobre diseños: incluyen ejemplos que no son demasiado grandes ni complicados de entender, pero que no son triviales.

Si ahora está convencido de que vale la pena estudiar sistemas triples, es posible que aún se esté preguntando sobre los sistemas triples Steiner en particular. Hemos visto que el método de repetición de bloques nos permite construir un sistema triple para cualquiera\(λ\) si primero tenemos un sistema triple con\(λ = 1\), por lo que los sistemas triples Steiner serán el tipo de sistema triple más raro, y por lo tanto son de particular interés.

En el resto de esta sección, probaremos el resultado de Kirkman caracterizando los valores\(v\) para los que\((v)\) existe un STS. Para ello, requeriremos dos resultados sobre la existencia de tipos especiales de cuadrados latinos. ¡Hay muchas conexiones en combinatoria!

Los tipos especiales de cuadrados latinos que requerimos serán simétricos: es decir, la entrada en fila\(i\) y columna\(j\) debe ser igual a la entrada en fila\(j\), columna\(i\). También especificaremos las entradas en la diagonal principal: las posiciones para las que el número de fila y el número de columna son los mismos.

Lema\(\PageIndex{1}\)

Por cada impar\(n\), hay un cuadrado latino simétrico de orden\(n\) con\(1, 2, . . . , n\) aparecer en ese orden por debajo de la diagonal principal.

Prueba

Hacer las entradas de la primera fila

\[1,\dfrac{(n + 3)}{2}, 2,\dfrac{(n + 5)}{2}, 3, . . . ,\dfrac{(n − 1)}{2}, n,\dfrac{(n + 1)}{2}.\]

Para\(i ≥ 2\), las entradas de fila\(i\) serán las entradas de fila\(i − 1\) desplazadas una posición a la izquierda.

Claramente, todas las entradas en cualquier fila son distintas. Además, dado que se necesitan\(n\) turnos a la izquierda para volver al punto de partida, todas las entradas en cualquier columna deben ser distintas.

Dado que la entrada en fila\(a\), columna\(b\) se mueve a la\(a + 1\) columna de entrada en fila\(b − 1 (\text{mod } n)\), las posiciones en las que aparece esta entrada serán precisamente las posiciones\((x, y)\) para las que\(x+y ≡ a + b (\text{mod } n)\). Ya que\(i + j = j + i\), la entrada en columna\(i\) de fila\(j\) será la misma que la entrada en columna\(j\) de fila\(i\). Así, el cuadrado latino es simétrico.

El mismo argumento muestra que la entrada en fila\(i\) y columna\(i\) será la entrada en posición\(2i − 1 (\text{mod } n)\) de fila\(1\). Pero esto es precisamente donde se\(i\) ha colocado, por lo que esta entrada será\(i\), como se desee.

Ejemplo\(\PageIndex{2}\)

Cuando\(n = 11\), aquí está el cuadrado latino (simétrico) construido en la prueba de Lema 18.1.1:

\[ 1\; \; 7\; \; 2\; \; 8\; \; 3\; \; 9\; \; 4\; \; 10\; \; 5\; \; 11\; \; 6 \\ 7\; \; 2\; \; 8\; \; 3\; \; 9\; \; 4\; \; 10\; \; 5\; \; 11\; \; 6 \;\;1 \\ 2\; \; 8\; \; 3\; \; 9\; \; 4\; \; 10\; \; 5\; \; 11\; \; 6 \;\;1 \;\; 7 \\ 8\; \; 3\; \; 9\; \; 4\; \; 10\; \; 5\; \; 11\; \; 6 \;\;1 \;\; 7 \; \;2 \\ 3\; \; 9\; \; 4\; \; 10\; \; 5\; \; 11\; \; 6 \;\;1 \;\; 7 \; \;2 \; \;8 \\ 9\; \; 4\; \; 10\; \; 5\; \; 11\; \; 6 \;\;1 \;\; 7 \; \;2 \; \;8 \;\;3 \\ 4\; \; 10\; \; 5\; \; 11\; \; 6 \;\;1 \;\; 7 \; \;2 \; \;8 \;\;3 \;\;9\\ 10\; \; 5\; \; 11\; \; 6 \;\;1 \;\; 7 \; \;2 \; \;8 \;\;3 \;\;9 \;\;4 \\ 5\; \; 11\; \; 6 \;\;1 \;\; 7 \; \;2 \; \;8 \;\;3 \;\;9 \;\;4 \;\;10 \\ 11\; \; 6 \;\;1 \;\; 7 \; \;2 \; \;8 \;\;3 \;\;9 \;\;4 \;\;10 \;\; 5 \\ 6 \;\;1 \;\; 7 \; \;2 \; \;8 \;\;3 \;\;9 \;\;4 \;\;10 \;\; 5 \;\; 11 \]

Se puede ver que esta construcción no funcionará cuando\(n\) es par, ya que los valores de algunas de las entradas dadas en las fórmulas no serían enteros. De hecho, no es posible construir un cuadrado latino simétrico de orden\(n\) con las entradas\(1, . . . n\) bajando la diagonal principal cuando\(n\) es par. Afortunadamente, es posible construir algo similar que logre lo que vamos a requerir.

Lema\(\PageIndex{2}\)

Por cada par\(n\), hay un cuadrado latino simétrico de orden\(n\) con los valores que\(1, . . . , \dfrac{n}{2}, 1, . . . , \dfrac{n}{2}\) aparecen en ese orden por debajo de la diagonal principal.

Prueba

Hacer las entradas de la primera fila.

\[ 1,\dfrac{(n + 2)}{2}, 2,\dfrac{(n + 4)}{2}, 3, . . . ,\dfrac{(n − 2)}{2}, n. \]

Para\(i ≥ 2\), las entradas de fila\(i\) serán las entradas de fila\(i − 1\) desplazadas una posición a la izquierda.

Los mismos argumentos que en la prueba de Lema 18.1.1 muestran que se trata de un cuadrado latino simétrico. La entrada en fila\(i\) y columna\(i\) será la entrada en posición\(2i − 1 (\text{mod } n)\) de fila\(1\). Estas son las entradas\(1, 2, . . . , \dfrac{n}{2}\) y desde la posición

\[ \dfrac{2(n + 2j)}{2} − 1 ≡ 2j − 1 (\text{mod } n) \]

las entradas en posiciones\((j, j)\) y\((\dfrac{(n + 2j)}{2},\dfrac{(n + 2j)}{2})\) serán las mismas, por lo que cada una de estas entradas se repetirá en el mismo orden.

Ejemplo\(\PageIndex{3}\)

Cuando\(n = 10\), aquí está el cuadrado latino (simétrico) construido en la prueba de Lema 18.1.2:

\[1\; \; 6\; \; 2\; \; 7\; \; 3\; \; 8\; \; 4\; \; 9\; \; 5\; \; 10\\ 6\; \; 2\; \; 7\; \; 3\; \; 8\; \; 4\; \; 9\; \; 5\; \; 10 \;\;1\\ 2\; \; 7\; \; 3\; \; 8\; \; 4\; \; 9\; \; 5\; \; 10\;\;1\; \; 6 \\ 7\; \; 3\; \; 8\; \; 4\; \; 9\; \; 5\; \; 10 \;\; 1\; \; 6\; \; 2\\ 3\; \; 8\; \; 4\; \; 9\; \; 5\; \; 10 \;\; 1\; \; 6\; \; 2\; \; 7\\ 8\; \; 4\; \; 9\; \; 5\; \; 10 \;\; 1\; \; 6\; \; 2\; \; 7\; \; 3\\ 4\; \; 9\; \; 5\; \; 10 \;\; 1\; \; 6\; \; 2\; \; 7\; \; 3\; \; 8\\ 9\; \; 5\; \; 10 \;\; 1\; \; 6\; \; 2\; \; 7\; \; 3\; \; 8\; \; 4\\ 5\; \; 10 \;\; 1\; \; 6\; \; 2\; \; 7\; \; 3\; \; 8\; \; 4\; \; 9\\ 10 \;\; 1\; \; 6\; \; 2\; \; 7\; \; 3\; \; 8\; \; 4\; \; 9\; \; 5\]

Ahora estamos listos para caracterizar los valores de\(v\) para los que existe un STS\((v)\).

Teorema\(\PageIndex{1}\)

Un STS\((v)\) existe si y solo si\(v ≡ 1, 3 (\text{mod } 6)\).

Prueba

Demostramos las dos implicaciones por separado.

\((⇒)\)Supongamos que\((v)\) existe un STS. Entonces por el Teorema 17.1.3, los valores

\[λ\dfrac{v-1}{k-1} = \dfrac{v-1}{2} \text{ and } λ\dfrac{v(v-1)}{k(k-1)} = \dfrac{v(v-1)}{6} \]

deben ser enteros. La primera de estas condiciones nos dice que\(v\) debe ser extraño, así debe ser\(1\),\(3\), o\(5 (\text{mod } 6)\). Si\(v ≡ 5 (\text{mod } 6)\), entonces\(v = 6q + 5\) para algunos\(q\), entonces

\ [\ dfrac {v (v − 1)} {6} =\ dfrac {(6q + 5) (6q + 4)} {6}.]

Ya que\(6q + 5\) ni ni\(6q + 4\) es un múltiplo de\(3\), esto no será un entero. Así, la segunda condición elimina la posibilidad\(v ≡ 5 (\text{mod } 6)\). Por lo tanto,\(v ≡ 1, 3 (\text{mod } 6)\).

\((⇐)\)Supongamos que\(v ≡ 1, 3 (\text{mod } 6)\). Damos construcciones separadas de sistemas triples Steiner en\(v\) puntos, dependiendo de la clase de congruencia de\(v\). Utilizaremos el enfoque teórico de la gráfica al problema, por lo que nuestro objetivo es encontrar clases de color para los bordes de\(K_v\) tal manera que cada clase de color consista en un\(K_3\).

\(v ≡ 3 (\text{mod } 6)\)Diga\(v = 6q + 3\). Etiquetar los vértices de\(K_{6q+3}\) con

\[u_1, . . . , u_{2q+1}; v_1, . . . , v_{2q+1}; and w_1, . . . , w_{2q+1}.\]

Por Lema 18.1.1, hay un cuadrado latino de orden\(2q + 1\) en el que para cada\(1 ≤ i ≤ 2q + 1\), la entrada\(i\) aparece en posición\((i, i)\).

Para\(1 ≤ i\),\(j ≤ 2q + 1\) con\(i \neq j\), si la entrada en posición\((i, j)\) de este cuadrado latino es\(\ell\), entonces usa nuevos colores para colorear los bordes que unen los vértices en cada uno de los siguientes conjuntos:

\[\{u_i , u_j , v_{\ell} \}; \{v_i , v_j , w_{\ell} \}; \text{ and } \{w_i , w_j , u_{\ell}\}.\]

Dado que el cuadrado latino era simétrico, tanto la posición\((i, j)\) como la posición\((j, i)\) dan lugar a las mismas clases de color. Ya que consideramos cada par\(i \neq j\), cada borde de la forma\(u_iu_j\)\(v_iv_j\), o\(w_iw_j\) ha sido coloreado (debemos tener\(i \neq j\) para que exista tal borde). Dado que el cuadrado es latino, cada entrada posible\(\ell\) ocurre en algún lugar de fila\(i\), por lo que cada borde de la forma\(u_iv_{\ell}\)\(v_iw_{\ell}\),, o\(w_iu_{\ell}\) ha sido coloreado, excepto que no miramos la entrada del cuadrado latino en la posición\((i, j)\), donde\(i = j\). Sabemos que la entrada en posición\((i, i)\) es\(i\), entonces los bordes de la forma\(u_iv_i\),\(v_iw_i\), y\(w_iu_i\) son los únicos bordes que aún no han sido coloreados.

Para cada uno\(1 ≤ i ≤ 2q + 1\), haga que los bordes se unan\(u_i\)\(v_i\), y\(w_i\) en una clase de color.

Ahora todos los bordes de\(K_{6q+3}\) han sido coloreados, y cada clase de color forma una\(K_3\), así que hemos construido un sistema triple Steiner.

\(v ≡ 1 (\text{mod } 6)\). Diga\(v = 6q + 1\). Etiquetar los vértices de\(K_{6q+1}\) con

\[u_1, . . . , u_{2q}; v_1, . . . , v_{2q}; and w_1, . . . , w_{2q}; x.\]

Por Lema 18.1.2, hay un cuadrado latino de orden\(2q\) en el que para cada\(1 ≤ i ≤ q\), la entrada\(i\) aparece en posición\((i, i)\), y para cada\(q + 1 ≤ i ≤ 2q\),\(i − q\) aparece en posición\((i, i)\).

Para\(1 ≤ i\),\(j ≤ 2q\) con\(i \neq j\), si la entrada en posición\((i, j)\) de este cuadrado latino es\(\ell\), entonces usa nuevos colores para colorear los bordes que unen los vértices en cada uno de los siguientes conjuntos:

\[\{u_i , u_j , v_{\ell} \}; \{v_i , v_j , w_{\ell} \}; \text{ and } \{w_i , w_j , u_{\ell}\}.\]

Dado que el cuadrado latino era simétrico, tanto la posición\((i, j)\) como la posición\((j, i)\) dan lugar a las mismas clases de color. Ya que consideramos cada par\(i \neq j\), cada borde de la forma\(u_iu_j\)\(v_iv_j\), o\(w_iw_j\) ha sido coloreado (debemos tener\(i \neq j\) para que exista tal borde). Dado que el cuadrado es latino, cada entrada posible\(\ell\) ocurre en algún lugar de fila\(i\), por lo que cada borde de la forma\(u_iv_{\ell}\)\(v_iw_{\ell}\),, o\(w_iu_{\ell}\) ha sido coloreado, excepto que no miramos la entrada del cuadrado latino en la posición\((i, j)\), donde\(i = j\). Sabemos que la entrada en posición\((i, i)\) es\(i\) (if\(i ≤ q\)) o\(i − q\) (if\(i > q\)), así que los únicos bordes que aún no han sido coloreados son los bordes de la forma\(u_iv_i\)\(v_iw_i\), y\(w_iu_i\) cuándo\(i ≤ q\) y\(u_iv_{i−q}\)\(v_iw_{i−q}\), y\(w_iu_{i−q}\) cuándo \(i > q\), así como cada incidente de borde con\(x\).

Para cada uno\(1 ≤ i ≤ q\), haga que los bordes se unan\(u_i\)\(v_i\), y\(w_i\) en una clase de color. Observe que entre los bordes restantes con los que no inciden\(x\), cada vértice que no\(x\) sea un vértice final de precisamente uno de los bordes. Por ejemplo, si\(i ≥ q\) entonces\(u_iv_{i−q}\) es uno de estos bordes, mientras que si\(i < q\),\(w_{i+q}u_i\) es uno de estos bordes, entonces de cualquier manera,\(u_i\) es un vértice final de precisamente uno de estos bordes. Por lo tanto, si por cada\(q + 1 ≤ i ≤ 2q\) usamos nuevos colores para colorear los bordes que unen los vértices en cada uno de los siguientes conjuntos:

\[{u_i , v_{i−q}, x}; {v_i , w_{i−q}, x}; and {w_i , u_{i−q}, x},\]

cada incidente de borde con\(x\) (así como todos nuestros otros bordes restantes) habrá sido coloreado.

Ahora todos los bordes de\(K_{6q+1}\) han sido coloreados, y cada clase de color forma una\(K_3\), así que hemos construido un sistema triple Steiner.

Ejemplo\(\PageIndex{4}\)

Utilizaremos el método del Teorema 18.1.1 para construir un STS (\(15\)).

Tenemos\(15 = 6(2) + 3\), entonces\(q = 2\). Los puntos de nuestro diseño serán\(u_i\)\(v_i\), y\(w_i\) para\(1 ≤ i ≤ 2q + 1 = 5\), y requeriremos un cuadrado latino simétrico de orden\(5\). Aquí está la plaza:

\[1\; \; 4\; \; 2\; \; 5\; \; 3\\ 4\; \; 2\; \; 5\; \; 3\; \; 1\\ 2\; \; 5\; \; 3\; \; 1\; \; 4 \\ 5\; \; 3\; \; 1\; \; 4\; \; 2\\ 3\; \; 1\; \; 4\; \; 2\; \; 5\]

Aquí están los bloques que formamos a partir de esta plaza latina:

\[ \{u_1, u_2, v_4\}, \{v_1, v_2, w_4\}, \{w_1, w_2, u_4\},\;\;\;\;\;\; \{u_1, u_3, v_2\}, \{v_1, v_3, w_2\}, \{w_1, w_3, u_2\}, \\ \{u_1, u_4, v_5\}, \{v_1, v_4, w_5\}, \{w_1, w_4, u_5\},\;\;\;\;\;\; \{u_1, u_5, v_3\}, \{v_1, v_5, w_3\}, \{w_1, w_5, u_3\}, \\ \{u_2, u_3, v_5\}, \{v_2, v_3, w_5\}, \{w_2, w_3, u_5\},\;\;\;\;\;\; \{u_2, u_4, v_3\}, \{v_2, v_4, w_3\}, \{w_2, w_4, u_3\}, \\ \{u_2, u_5, v_1\}, \{v_2, v_5, w_1\}, \{w_2, w_5, u_1\},\;\;\;\;\;\; \{u_3, u_4, v_1\}, \{v_3, v_4, w_1\}, \{w_3, w_4, u_1\}, \\ \{u_3, u_5, v_4\}, \{v_3, v_5, w_4\}, \{w_3, w_5, u_4\},\;\;\;\;\;\; \{u_4, u_5, v_2\}, \{v_4, v_5, w_2\}, \{w_4, w_5, u_2\}, \\ \{u_1, v_1, w_1\}, \{u_2, v_2, w_2\}, \{u_3, v_3, w_3\}, \{u_4, v_4, w_4\}, \{u_5, v_5, w_5\} \]

Después de resolver el problema de Woolhouse, Kirkman notó que su construcción de un STS (\(15\)) tenía una propiedad muy bonita. Desafió a otros a llegar a esta solución en el siguiente problema que publicó en la\(1850\) edición del Diario de Damas y Caballeros:

Quince señoritas en una escuela salen tres al corriente durante siete días seguidos: se requiere organizarlas diariamente para que no dos caminen dos veces al día.

Esto se ha dado a conocer como el problema de la colegiala de Kirkman.

Si bien este problema comienza requiriendo un STS (\(15\)), tiene el requisito adicional de que debe ser posible particionar los bloques de este diseño (las filas de señoritas) en siete grupos (de cinco cuadras cada uno) para que cada punto (jovencita) aparezca exactamente una vez en cada grupo. Este requisito extra viene del hecho de que cada una de las señoritas debe salir todos los días, y sólo puede estar en una fila en un día determinado.

Definición: Diseño Resoluble

Un BIBD es un diseño resoluble si los bloques del diseño se pueden particionar en conjuntos, cada uno de los cuales forma una partición del conjunto de puntos del BIBD. Un sistema triple Kirkman es un sistema triple Steiner resoluble.

Observe que como cada bloque tiene\(3\) puntos en él, un sistema triple Kirkman solo es posible si\(\dfrac{v}{3}\) es un entero. Dado que un sistema triple Kirkman es también un sistema triple Steiner, esto significa que debemos tener\(v ≡ 3 (\text{mod } 6)\).

Hay siete sistemas triples de Kirkman no isomórficos de orden\(15\).

También se sabe que los sistemas triples Kirkman existen siempre que sea\(v ≡ 3 (\text{mod } 6)\).

Teorema\(\PageIndex{2}\) (Chaudhury-Wilson, 1971)

Hay un sistema triple Kirkman siempre que sea\(v ≡ 3 (\text{mod } 6)\).

Ejercicio\(\PageIndex{1}\)

1) Porque\(v = 37\), da el cuadrado latino que tendrías que usar para construir un sistema triple Steiner usando el método descrito en la prueba del Teorema 18.1.1.

2) Porque\(v = 39\), da el cuadrado latino que tendrías que usar para construir un sistema triple Steiner usando el método descrito en la prueba del Teorema 18.1.1.

3) Para\(v = 19\), utilizar el método descrito en la prueba del Teorema 18.1.1 para construir un sistema triple Steiner.

4) ¿Se construye el STS (\(15\)) en el Ejemplo 18.1.4 un sistema triple Kirkman? Explica tu respuesta.

[Pista: Piense en argumentos de tipo Paloma.]

5) Encontrar todos los valores\(λ\) para los cuales existe un sistema triple en seis variedades. Para cada uno de esos valores de\(λ\), ya sea dar un diseño o explicar cómo construirlo.

[Pista: Comience mostrando que si existe tal diseño, sus parámetros son\((2r, 6, r, 3, \dfrac{2r}{5})\). Entonces determina qué valores\(r\) pueden asumir. Finalmente, use algunos resultados sobre cómo construir diseños.]

6) Construir un diseño STS (\(13\)). Muestra tu trabajo.

7) Dejar\(v = 21\).

(a) Anote el cuadrado latino que usaría para construir un sistema triple Steiner (para este valor de\(v\)) utilizando el método descrito en la prueba del Teorema 18.1.1.

b) Para el sistema triple Steiner resultante, el cual triples contiene:

(i) ambos\(u_1\) y\(u_3\)?

ii) ambos\(v_2\) y\(w_7\)?

iii) ambos\(u_3\) y\(w_4\)?

iv) ambos\(v_5\) y\(w_5\)?

(v)\(w_3\)?

8) Dejar\(v = 27\).

(a) Anote el cuadrado latino que usaría para construir un sistema triple Steiner (para este valor de\(v\)) utilizando el método descrito en la prueba del Teorema 18.1.1.

b) Para el sistema triple Steiner resultante, el cual triples contiene:

(i) ambos\(v_3\) y\(u_8\)?

ii) ambos\(u_4\) y\(w_4\)?

iii) ambos\(u_5\) y\(w_4\)?

iv)\(v_2\)?

v) ambos\(v_2\) y\(v_5\)?