Habitación cuadrada

Un cuadrado Room , llamado así en honor a Thomas Gerald Room , es una matriz de n por n llena con n  +  1 símbolos diferentes de tal manera que:

1. Cada celda de la matriz está vacía o contiene un par no ordenado del conjunto de símbolos.
2. Cada símbolo aparece exactamente una vez en cada fila y columna de la matriz.
3. Cada par de símbolos no ordenados aparece en exactamente una celda de la matriz.

Un ejemplo, un cuadrado de Room de orden siete, si el conjunto de símbolos son números enteros del 0 al 7:

Se sabe que existe un cuadrado (o cuadrados) de Room si y solo si n es impar pero no 3 ni 5.

Un cuadrado de Room de orden n es equivalente a un par de cuadrados latinos simétricos 'ortogonales' de orden n . Dos cuadrados latinos simétricos no pueden ser ortogonales con respecto a la definición de contener cada par ordenado de símbolos; sin embargo, la unión de los cuadrados contendrá cada par no ordenado exactamente una vez por encima de la diagonal.

El cuadrado latino de 'fila' utiliza un etiquetado de filas del cuadrado de la habitación como símbolos, por ejemplo${\textstyle \{r_{0},r_{1},\dots ,r_{n-1}\}}$y etiqueta la célula${\textstyle (i,j)}$(y${\textstyle (j,i)}$) con${\textstyle r_{a}}$si el par no ordenado${\textstyle \{i,j\}}$aparece en el cuadrado de la habitación en la fila${\textstyle a}$. Además, el símbolo adicional del cuadrado de la habitación, a veces denotado${\textstyle \infty }$Se elimina el símbolo y las celdas correspondientes del cuadrado latino se rellenan con el símbolo restante del par. El cuadrado latino de la columna se construye de forma similar.

Por ejemplo, los cuadrados latinos de filas y columnas del cuadrado de habitación de orden 7 anterior:

Un cuadrado de habitación es equivalente a un par de 1-factorizaciones ortogonales de${\textstyle K_{r+1}}$, el gráfico completo en${\textstyle r+1}$vértices. Al leer las filas del cuadrado de la habitación como las aristas de un 1-factor, se obtiene una 1-factorización. El par ortogonal proviene de los 1-factores de la columna.

El cuadrado de Room de orden 7 fue utilizado por Robert Richard Anstice para proporcionar soluciones adicionales al problema de la colegiala de Kirkman a mediados del siglo XIX, y Anstice también construyó una familia infinita de cuadrados de Room, pero sus construcciones no atrajeron la atención. ^{[ 1 ]} Thomas Gerald Room reinventó los cuadrados de Room en una nota publicada en 1955, ^{[ 2 ]} y estos pasaron a ser nombrados en su honor. En su artículo original sobre el tema, Room observó que n debe ser impar y distinto de 3 o 5, pero no se demostró que estas condiciones fueran necesarias y suficientes hasta el trabajo de WD Wallis en 1973. ^{[ 3 ]}

Antes de la publicación del artículo de Room, los directores de torneos de bridge duplicado ya utilizaban los cuadrados de Room para la organización de los torneos. En este contexto, se conocen como rotaciones de Howell. Las columnas del cuadrado representan las mesas, cada una de las cuales contiene una distribución de cartas que juega cada pareja de equipos que se reúne en esa mesa. Las filas del cuadrado representan las rondas del torneo, y los números dentro de las celdas del cuadrado representan los equipos que deben enfrentarse en la mesa y ronda representadas por dicha celda.

Archbold y Johnson utilizaron cuadrados de Room para construir diseños experimentales. ^{[ 4 ]}

Existen conexiones entre los cuadrados de Room y otros objetos matemáticos, incluidos los cuasigrupos , los cuadrados latinos , las factorizaciones de grafos y los sistemas triples de Steiner . ^{[ 5 ]}

• Diseño combinatorio
• cuadrado mágico
• Matrices cuadradas

• Dinitz, JH; Stinson, DR (1992), "Room squares and related designs", en Dinitz, JH; Stinson, DR (eds.), Contemporary Design Theory: A Collection of Surveys , Wiley–Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons , pp. 137–204 , ISBN  0-471-53141-3
• Weisstein, Eric W. , "Room Square" , MathWorld