17.1: Diseños de Bloques Incompletos Balanceados (BIBD)

Supongamos que tienes\(7\) posibles tratamientos para una enfermedad, que esperas que puedan funcionar bien individualmente o en combinación. Te gustaría probar cada combinación posible de ellos, pero el número de subconjuntos (no vacíos) del conjunto de\(7\) tratamientos es\(2^7 − 1 = 127\), y solo tienes\(7\) ratones en el laboratorio que tienen esta enfermedad. Usted cree que usar un par de tratamientos juntos tendrá un impacto más significativo que agregar más de los tratamientos, pero incluso probar cada par de tratamientos en un ratón diferente requeriría\(\binom{7}{2} = 21\) ratones.

Aquí hay una estrategia que podrías probar: dar a cada uno de los ratones\(3\) de los tratamientos, de acuerdo con el siguiente esquema. Para\(1 ≤ i ≤ 7\), los tratamientos dados al ratón\(i\) serán los elementos del\(i^{\text{th}}\) conjunto en la siguiente lista

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

Una cuidadosa lectura de este esquema demostrará que cada par de tratamientos se usa en conjunto precisamente en uno de los ratones.

Definición: Diseño y Bloque

Un diseño es un par\((V, \mathcal{B})\), donde\(V\) es un conjunto finito de puntos (variedades) y\(B\) es una colección de subconjuntos de\(V\), llamados bloques del diseño

Esta definición de un diseño es demasiado amplia para ser de mucho interés sin restricciones adicionales, pero se han estudiado una variedad de restricciones diferentes.

Notación

Usamos\(v\) para\(b\) denotar\(|V|\) y denotar\(|\mathcal{B}|\).

Definición: Diseño Regular, Uniforme y Equilibrado

Un diseño regular es un diseño en el que cada punto aparece en el mismo número de bloques,\(r\).

Un diseño uniforme es un diseño en el que cada bloque contiene el mismo número de puntos,\(k\).

Un diseño equilibrado es un diseño en el que cada par de puntos aparecen juntos en el mismo número de bloques,\(λ\).

Ejemplo\(\PageIndex{1}\)

En nuestros tratamientos de enfermedades para los ratones, tenemos\(V = \{1, 2, 3, 4, 5, 6, 7\}\)

\(\mathcal{B} = \{\{1, 2, 3\}, \{1, 4, 5\}, \{1, 6, 7\}, \{2, 4, 6\}, \{2, 5, 7\}, \{3, 4, 7\}, \{3, 5, 6\}\}.\)

Se trata de un diseño regular, uniforme y equilibrado. En este diseño\(v = 7\),\(b = 7\),\(r = 3\),\(k = 3\), y\(λ = 1\).

Un diseño regular, uniforme y equilibrado puede denominarse\((b, v, r, k, λ)\) -diseño. Por lo que nuestros tratamientos de enfermedades para los ratones formaron un\((7, 7, 3, 3, 1)\) -diseño.

Un\(b, v, r, k, λ)\) -diseño se llama completo si\(v = k\). En este caso, cada bloque contendrá cada punto. Un\((b, v, r, k, λ)\) -diseño se llama trivial si\(k = 1\). En este caso, cada bloque consiste en un solo punto, y no aparecen puntos juntos en un bloque. El caso también\(k = 2\) es bastante trivial ya que en este caso, los bloques del diseño deben consistir en los\(\binom{v}{2}\) pares de elementos de\(v\), cada\(λ\) vez que ocurren.

Definición: Diseño de Bloques Incompletos Balanceados (BIBD)

Un diseño de bloques incompletos balanceados (BIBD) es un diseño regular, uniforme y equilibrado que no es completo. Entonces es un\((b, v, r, k, λ)\) -diseño con\(k < v\).

Aunque esta definición incluye la posibilidad\(k = 1\) o\(k = 2\), estos no son casos interesantes, y por lo general pueden ignorarse

Ejemplo\(\PageIndex{2}\)

Aquí hay otro BIBD. Este tiene parámetros\((20, 16, 5, 4, 1)\).

\[\begin{equation} \begin{split} &\{a, b, c, d\}, &\;\;\{e, f, g, h\}, &\;\;\{i, j, k, l\}, &\;\;\{m, n, o, p\}, &\;\;\{a, e, i, m\}, &\;\;\{a, f, j, n\}, \;\;&\{a, g, k, o\},\\ &\{a, h, l, p\}, &\;\;\{b, e, j, o\}, &\;\;\{b, f, i, p\}, &\;\;\{b, g, l, m\}, &\;\;\{b, h, k, n\}, &\;\;\{c, e, l, o\}, \;\;&\{c, f, k, p\},\\ &\{c, g, i, n\}, &\;\;\{c, h, j, m\}, &\;\;\{d, e, k, n\}, &\;\;\{d, f, l, m\}, &\;\;\{d, g, j, p\}, &\;\;\{d, h, i, o\} \end{split} \end{equation}\]

Teorema\(\PageIndex{1}\)

Si existe un\((b, v, r, k, λ)\) -diseño, entonces\(bk = vr\) y

\[r(k − 1) = λ(v − 1)\]

Prueba

Para la primera ecuación, contamos el número total de apariciones de cada punto en el diseño (incluyendo repeticiones) de dos maneras. Este es otro ejemplo de contar pares ordenados a partir de un producto cartesiano, como ya hemos comentado anteriormente.

Primero, hay\(b\) bloques, cada uno de los cuales tiene\(k\) puntos en él. Entonces la respuesta será\(bk\).

Segundo, hay\(v\) puntos, cada uno de los cuales aparece\(r\) veces. Entonces la respuesta será\(vr\).

Por lo tanto,\(vr = bk\).

Para la segunda ecuación, fijamos un punto\(p\) y contamos el número de puntos con los que\(p\) aparece en un bloque, de dos maneras.

Primero,\(p\) aparece en\(r\) bloques. En cada uno de estos, hay\(k−1\) puntos además\(p\). Entonces la respuesta será\(r(k − 1)\).

Segundo, por cada punto\(p' ∈ V\) con\(p' \neq p\), el punto\(p'\) aparece con\(p\) en\(λ\) diferentes bloques. Ya que hay\(v − 1\) opciones para\(p'\), la respuesta será\(λ(v − 1)\)

Por lo tanto,\(r(k − 1) = λ(v − 1)\).

Con un poco de cálculo, los resultados del Teorema 17.1.1 nos dicen que

\[r = \dfrac{λ(v − 1)}{k −1} \label{17.1.4}\]

y

\[b = \dfrac{vr}{k} = \dfrac{λv(v − 1)}{k(k − 1)} \label{17.1.5}\]

Así, si sabemos que un diseño es regular, uniforme y equilibrado, entonces los parámetros\(r\) y se\(b\) pueden determinar a partir de los parámetros\(v\),\(k\), y\(λ\). Por lo tanto, a menudo acortamos nuestra notación y nos referimos a un BIBD\((v, k, λ)\).

Teorema\(\PageIndex{2}\)

Un BIBD\((v, k, λ)\) equivale a colorear los bordes del multígrafo\(λK_v\) (el multígrafo en el que cada borde de\(K_v\) ha sido reemplazado por\(λ\) copias de ese borde) para que los bordes de cualquier color formen un\(K_k\).

Prueba

Dada una coloración de bordes\(λK_v\) como se describe, definir los puntos del diseño para ser el conjunto de vértices del multígrafo, y para cada color, crear un bloque cuyos vértices son los vértices del\(K_k\) que tiene ese color. Todos estos bloques tendrán cardinalidad\(k\). Cada vértice tiene valencia\(λ(v − 1)\), y cada\(K_k\) color que contiene ese vértice utilizará\(k − 1\) los bordes incidentes con ese vértice, por lo que cada vértice aparecerá en

\[r = \dfrac{λ(v − 1)}{(k − 1)}\]

bloques. Ahora bien, cualquier borde del\(λK_v\) mosto aparece en algunos\(K_k\) (el coloreado con el color de ese borde). Así, para cualquier par de puntos, estos vértices están unidos por\(λ\) aristas cada una de las cuales aparece en algunos\(K_k\), por lo que estos puntos deben aparecer juntos en\(λ\) de las\(K_k\) subgráficas, es decir,\(λ\) de los bloques.

De igual manera, dado un BIBD\((v, k, λ)\), y un multígrafo\(λK_v\), etiquetar los vértices de\(K_v\) con los puntos del diseño. Para cada bloque del diseño, use un nuevo color para colorear los bordes de un\(K_k\) que conecte los puntos en ese bloque. Habrá bastantes aristas incoloras uniendo estos puntos, ya que cada par de puntos aparecen juntos exactamente en\(λ\) bloques, y hay\(λ\) aristas uniendo los vértices correspondientes. De hecho, un conteo cuidadoso puede mostrar que esto dará como resultado colorear cada borde del multígrafo.

Esto es más agradable en el caso donde\(λ = 1\), cuando el BIBD corresponde a una coloración de bordes de\(K_v\).

Una coloración de los bordes de una gráfica (o multígrafo) a menudo se denomina descomposición de la gráfica (o multígrafo), ya que podemos pensar en las clases de color como conjuntos de bordes cuya unión forma todo el conjunto de bordes de la gráfica.

Estos proporcionan formas alternas de pensar en diseños que pueden ser más intuitivos, y sin duda son más visuales. Las ecuaciones\ ref {17.1.4} y\ ref {17.1.5} conducen a condiciones numéricas on\(v\)\(k\),, y\(λ\) que deben cumplirse para que exista un BIBD\((v, k, λ)\).

Teorema\(\PageIndex{3}\)

Un BIBD\((v, k, λ)\) no puede existir a menos que

\(λ \dfrac{v − 1}{k − 1} \text{ and } λ \dfrac{v(v − 1)}{k(k − 1)}\)

son números enteros.

Prueba

Por Ecuación\ ref {17.1.4}, cada punto del diseño debe aparecer en

\(\dfrac{λ(v − 1)}{k −1} \)

bloques. Dado que un punto solo puede aparecer en un número integral de bloques, sigue el primer resultado.

Del mismo modo, Por Ecuación\ ref {17.1.5}, debe haber

\(\dfrac{λv(v − 1)}{k(k − 1)} \)

bloques en el diseño. Como no puede haber un número fraccional de bloques, sigue el segundo resultado.

Si bien estas condiciones son necesarias para la existencia de un BIBD, no hay garantía de que exista un BIBD con parámetros especificados, aunque esos parámetros cumplan con estas condiciones.

Ejemplo\(\PageIndex{3}\)

Los parámetros\(v = 15\),\(k = 5\),\(λ = 2\) satisfacen las condiciones del Teorema 17.1.3, pero no hay BIBD\((15, 5, 2)\).

No vamos a probar que tal diseño no existe ya que la prueba sería tediosa y poco esclarecedora. Verificaremos que los parámetros cumplan con las condiciones necesarias.

Tenemos

\(\dfrac{λ(v − 1)}{k −1} = \dfrac{2(14)}{4} = 7 \),

y

\(\dfrac{λv(v − 1)}{k(k − 1)} = 2 \cdot 15 \cdot \dfrac{14}{20} = 21 \).

Ambos son enteros, por lo que si existiera un diseño, cada punto aparecería en\(7\) bloques, y habría\(21\) bloques. Una búsqueda por computadora puede verificar que no existe tal diseño.

Ejercicio\(\PageIndex{1}\)

1) Mostrar que para cualquier BIBD\((v, k, λ)\), el número de aristas de\(λK_v\) es igual al número de aristas de\(K_k\) veces el número de bloques del diseño.

2) Supongamos que hay un BIBD\((16, 6, 3)\). ¿Cuántos bloques tiene? ¿En cuántos de esos bloques aparece cada punto?

3) Encuentra una coloración de bordes de\(K_5\) manera que los bordes de cualquier color formen un\(K_2\). ¿Cuáles son los parámetros del diseño al que corresponde esto?

4) Aquí están los bloques de un BIBD con\(λ = 1\):

\(\begin{equation} \begin{split} &B_1 = \{1, 2, 3\} \;\;&B_2 = \{1, 4, 7\} \;\;&B_3 = \{1, 5, 9\} \;\;&B_4 = \{1, 6, 8\}\\ &B_5 = \{4, 5, 6\} \;\;&B_6 = \{2, 5, 8\} \;\;&B_7 = \{2, 6, 7\} \;\;&B_8 = \{2, 4, 9\}\\ &B_9 = \{7, 8, 9\} \;\;&B_{10} = \{3, 6, 9\} \;\;&B_{11} = \{3, 4, 8\} \;\;&B_{12} = \{3, 5, 7\}. \end{split} \end{equation}\)

a) ¿Cuáles son los valores de\(v\),\(b\),\(k\), y\(r\) para este BIBD?

b) ¿Cuántos de los bloques contienen el elemento\(7\)?

c) ¿Cuántos de los bloques contienen ambos\(2\) y\(7\)?

d) ¿Qué bloques contienen el elemento\(5\)?

e) ¿Qué bloques contienen ambos\(5\) y\(8\)?

5) Supongamos que\(\mathcal{B}\) es un BIBD con\(v = 16\)\(k = 4\),, y\(r = 3\).

a) ¿Cuáles son los valores de\(b\) y\(λ\)?

b) ¿Puede decir si tal BIBD existe o no?

6) Un sorteo te permite ingresar eligiendo\(3\) números de\(\{1, . . . , 14\}\). Ganarás un premio si eliges dos de los tres números que empatarán. Demostrar que es posible garantizar un triunfo al tener\(14\) entradas en el sorteo. Explique si una estrategia similar funcionaría o no si se escogieran los números\(\{1, . . . , 21\}\).

[Pista: Usa el\((7, 7, 3, 3, 1)\) diseño.]