Artículos

4.4: Cuadrados latinos - Matemáticas


Definición: cuadrado latino

A Plaza latina de orden (n ) es una cuadrícula (n veces n ) llena de (n ) símbolos para que cada símbolo aparezca una vez en cada fila y columna.

Ejemplo ( PageIndex {1} )

Aquí hay un cuadrado latino de orden 4:

Usualmente usamos los enteros (1 ldots n ) para los símbolos. Hay muchos, muchos cuadrados latinos de orden (n ), por lo que vale la pena limitar el número acordando no contar los cuadrados latinos que son "realmente iguales" como diferentes. La forma más sencilla de hacer esto es considerar reducido Cuadrados latinos. Un cuadrado latino reducido es aquel en el que la primera fila es (1 ldots n ) (en orden) y la primera columna es igualmente (1 ldots n ).

Ejemplo ( PageIndex {2} )

Considere este cuadrado latino:

4231
2413
1342
3124

El orden de las filas y columnas no es realmente importante para la idea de un cuadrado latino. Si reordenamos las filas y columnas, podemos considerar que el resultado es, en esencia, el mismo cuadrado latino. Al reordenar las columnas, podemos convertir el cuadrado de arriba en esto:

1234
3412
2341
4123

Luego podemos intercambiar las filas dos y tres:

1234
2341
3412
4123

Este cuadrado latino está en forma reducida y es esencialmente el mismo que el original.

Otra forma sencilla de cambiar la apariencia de un cuadrado latino sin cambiar su estructura esencial es intercambiar los símbolos.

Ejemplo ( PageIndex {3} )

Comenzando con el mismo cuadrado latino que antes:

4231
2413
1342
3124

podemos intercambiar los símbolos 1 y 4 para obtener:

1234
2143
4312
3421

Ahora, si intercambiamos las filas tres y cuatro obtenemos:

1234
2143
3421
4312

Observe que este cuadrado latino está en forma reducida, pero no es igual que la forma reducida del ejemplo anterior, aunque comenzamos con el mismo cuadrado latino. Por lo tanto, es posible que queramos considerar que algunos cuadrados latinos reducidos son iguales entre sí.

Definición: clases isotópicas e isotópicas

Dos cuadrados latinos son isotópico si cada uno se puede convertir en el otro permutando las filas, columnas y símbolos. Esta relación de isotopía es una relación de equivalencia; las clases de equivalencia son las isotopía clases.

Los cuadrados latinos son aparentemente bastante difíciles de contar sin una potencia de cálculo sustancial. El número de cuadrados latinos se conoce solo hasta (n = 11 ). Estos son los primeros valores para todos los cuadrados latinos, cuadrados latinos reducidos y cuadrados latinos no isotópicos (es decir, el número de clases de isotopías):

(norte)TodasReducidoNo isotópico
1111
2211
31211
457642
5161280562

¿Cómo podemos producir un cuadrado latino? Si sabes qué es un grupo, debes saber que la tabla de multiplicar de cualquier grupo finito es un cuadrado latino. (Además, cualquier cuadrado latino es la tabla de multiplicar de un cuasigrupo.) Incluso si no ha encontrado grupos con ese nombre, es posible que conozca algunos. Por ejemplo, considerando los números enteros módulo (n ) bajo la suma, la tabla de suma es un cuadrado latino.

Ejemplo ( PageIndex {4} )

Ejemplo 4.3.6 Aquí está la tabla de suma para los números enteros módulo 6:

012345
123450
234501
345012
450123
501234

Ejemplo 4.3.7 Aquí hay otra forma de generar potencialmente muchos cuadrados latinos. Comience con la primera fila (1, ldots, n ). Considere los conjuntos (A_i = [n] barra invertida {i } ). Del ejercicio 1 en la sección 4.1 sabemos que este sistema de conjuntos tiene muchos DEGs; si (x_1, x_2, ldots, x_n ) es un DEG, podemos usarlo para la fila dos. En general, después de haber elegido las filas (1, ldots, j ), dejamos que (A_i ) sea el conjunto de enteros que aún no se han elegido para la columna (i ). Este sistema de conjunto tiene un DEG, que usamos para la fila (j + 1 ).

Definición 4.3.8 Suponga que (A ) y (B ) son dos cuadrados latinos de orden (n ), con entradas (A_ {i, j} ) y (B_ {i, j} ) en la fila (i ) y la columna (j ). Forme la matriz (M ) con entradas (M_ {i, j} = (A_ {i, j}, B_ {i, j}) ); Denotaremos esta operación como (M = A cup B ). Decimos que (A ) y (B ) son ortogonal si (M ) contiene todos (n ^ 2 ) pares ordenados ((a, b) ), (1 le a le n ), (1 le b le n ) , es decir, todos los elementos de ( {0,1, ldots, n-1 } times {0,1, ldots, n-1 } ).

Como veremos, es fácil encontrar cuadrados latinos ortogonales de orden (n ) si (n ) es impar; no es demasiado difícil encontrar cuadrados latinos ortogonales de orden (4k ), y difícil pero posible encontrar cuadrados latinos ortogonales de orden (4k + 2 ), con la excepción de los órdenes (2 ) y (6 ). En la década de 1700, Euler mostró que hay cuadrados latinos ortogonales de todos los órdenes excepto del orden (4k + 2 ), y conjeturó que no hay cuadrados latinos ortogonales de orden (6 ). En 1901, el matemático aficionado Gaston Tarry demostró que de hecho no hay ninguno de orden (6 ), al demostrar que todas las posibilidades para tales cuadrados latinos no eran ortogonales. En 1959 finalmente se demostró que hay cuadrados latinos ortogonales de todos los demás órdenes.

Teorema 4.3.9

Hay pares de cuadrados latinos ortogonales de orden (n ) cuando (n ) es impar.

Prueba

Esta prueba se puede abreviar utilizando ideas de teoría de grupos, pero presentaremos una versión autónoma. Considere la tabla de suma para el mod de suma (n ):

0 ( cdots ) (j ) ( cdots ) (n-1 )
00 ( cdots ) (j ) ( cdots ) (n-1 )
( vdots )
(I)(I) ( cdots ) (i + j ) ( cdots ) (n + i-1 )
( vdots )
(n-1 ) (n-1 ) ( cdots ) (n + j-1 ) ( cdots ) (n-2 )

Primero afirmamos que este (sin la primera fila y columna, por supuesto) es un cuadrado latino con los símbolos (0,1, ldots, n-1 ). Considere dos entradas en la fila (i ), digamos (i + j ) y (i + k ). Si (i + j equiv i + j pmod {n} ), entonces (j equiv k ), entonces (j = k ). Por lo tanto, todas las entradas de la fila (i ) son distintas, por lo que cada uno de (0,1, ldots, n-1 ) aparece exactamente una vez en la fila (i ). La prueba de que cada uno aparece una vez en cualquier columna es similar. Llame a este cuadrado latino (A ). (Tenga en cuenta que hasta ahora todo es cierto, ya sea que (n ) sea par o impar).

Ahora forme un nuevo cuadrado (B ) con entradas (B_ {i, j} = A_ {2i, j} = 2i + j ), donde por (2i ) y (2i + j ) significa esos valores mod (n ). Por tanto, la fila (i ) de (B ) es la misma que la fila (2i ) de (A ). Ahora afirmamos que, de hecho, las filas de (B ) son exactamente las filas de (A ), en un orden diferente. Para hacer esto, basta con mostrar que si (2i equiv 2k pmod {n} ), entonces (i = k ). Esto implica que todas las filas de (B ) son distintas y, por tanto, deben ser todas las filas de (A ).

Suponga sin pérdida de generalidad que (i ge k ). Si (2i equiv 2k pmod {n} ) entonces (n divide 2 (i-k) ). Dado que (n ) es impar, (n divide (i-k) ). Dado que (i ) y (k ) están en (0,1, ldots, n-1 ), (0 le i-k le n-1 ). De estos valores, solo (0 ) es divisible por (n ), entonces (i-k = 0 ). Por tanto, (B ) también es un cuadrado latino.

Para mostrar que (A cup B ) contiene todos (n ^ 2 ) elementos de ( {0,1, ldots, n-1 } times {0,1, ldots, n -1 } ), basta con mostrar que no hay dos elementos de (A cup B ) iguales. Suponga que ((i_1 + j_1,2i_1 + j_1) = (i_2 + j_2,2i_2 + j_2) ) (la aritmética es mod (n )). Luego, restando ecuaciones, (i_1 = i_2 ); con la primera ecuación esto implica (j_1 = j_2 ).

(cuadrado)

Ejemplo 4.3.10 Cuando (n = 3 ), $$ left [ matrix {0 & 1 & 2 cr 1 & 2 & 0 cr 2 & 0 & 1 cr} right] cup left [ matrix {0 & 1 & 2 cr 2 & 0 & 1 cr 1 & 2 & 0 cr} right] = left [ matrix {(0,0) & (1,1) & (2,2) cr (1,2) & (2,0) & (0,1) cr (2,1) y (0,2) y (1,0) cr} derecha]. $$

Un enfoque obvio para construir cuadrados latinos y pares de cuadrados latinos ortogonales es comenzar con cuadrados latinos más pequeños y usarlos para producir otros más grandes. Produciremos un cuadrado latino de orden (mn ) a partir de un cuadrado latino de orden (m ) y uno de orden (n ).

Sea (A ) un cuadrado latino de orden (m ) con símbolos (1, ldots, m ), y (B ) uno de orden (n ) con símbolos (1, ldots, n ). Sean (c_ {i, j} ), (1 le i le m ), (1 le j le n ), (mn ) nuevos símbolos. Forme una cuadrícula (mn times mn ) reemplazando cada entrada de (B ) con una copia de (A ). Luego reemplace cada entrada (i ) en esta copia de (A ) con (c_ {i, j} ), donde (j ) es la entrada de (B ) que fue reemplazada. Denotamos este nuevo cuadrado latino (A times B ). Aquí hay un ejemplo, combinando un cuadrado latino (4 times 4 ) con un cuadrado latino (3 times 3 ) para formar un cuadrado latino (12 times 12 ):}

(1)(2)(3)(4)
(2)(3)(4)(1)
(3)(4)(1)(2)
(4)(1)(2)(3)
(veces)
(1)(2)(3)
(2)(3)(1)
(3)(1)(2)
(=)
(c_ {1,1} ) (c_ {2,1} ) (c_ {3,1} ) (c_ {4,1} )
(c_ {2,1} ) (c_ {3,1} ) (c_ {4,1} ) (c_ {1,1} )
(c_ {3,1} ) (c_ {4,1} ) (c_ {1,1} ) (c_ {2,1} )
(c_ {4,1} ) (c_ {1,1} ) (c_ {2,1} ) (c_ {3,1} )
(c_ {1,2} ) (c_ {2,2} ) (c_ {3,2} ) (c_ {4,2} )
(c_ {2,2} ) (c_ {3,2} ) (c_ {4,2} ) (c_ {1,2} )
(c_ {3,2} ) (c_ {4,2} ) (c_ {1,2} ) (c_ {2,2} )
(c_ {4,2} ) (c_ {1,2} ) (c_ {2,2} ) (c_ {3,2} )
(c_ {1,3} ) (c_ {2,3} ) (c_ {3,3} ) (c_ {4,3} )
(c_ {2,3} ) (c_ {3,3} ) (c_ {4,3} ) (c_ {1,3} )
(c_ {3,3} ) (c_ {4,3} ) (c_ {1,3} ) (c_ {2,3} )
(c_ {4,3} ) (c_ {1,3} ) (c_ {2,3} ) (c_ {3,3} )
(c_ {1,2} ) (c_ {2,2} ) (c_ {3,2} ) (c_ {4,2} )
(c_ {2,2} ) (c_ {3,2} ) (c_ {4,2} ) (c_ {1,2} )
(c_ {3,2} ) (c_ {4,2} ) (c_ {1,2} ) (c_ {2,2} )
(c_ {4,2} ) (c_ {1,2} ) (c_ {2,2} ) (c_ {3,2} )
(c_ {1,3} ) (c_ {2,3} ) (c_ {3,3} ) (c_ {4,3} )
(c_ {2,3} ) (c_ {3,3} ) (c_ {4,3} ) (c_ {1,3} )
(c_ {3,3} ) (c_ {4,3} ) (c_ {1,3} ) (c_ {2,3} )
(c_ {4,3} ) (c_ {1,3} ) (c_ {2,3} ) (c_ {3,3} )
(c_ {1,1} ) (c_ {2,1} ) (c_ {3,1} ) (c_ {4,1} )
(c_ {2,1} ) (c_ {3,1} ) (c_ {4,1} ) (c_ {1,1} )
(c_ {3,1} ) (c_ {4,1} ) (c_ {1,1} ) (c_ {2,1} )
(c_ {4,1} ) (c_ {1,1} ) (c_ {2,1} ) (c_ {3,1} )
(c_ {1,3} ) (c_ {2,3} ) (c_ {3,3} ) (c_ {4,3} )
(c_ {2,3} ) (c_ {3,3} ) (c_ {4,3} ) (c_ {1,3} )
(c_ {3,3} ) (c_ {4,3} ) (c_ {1,3} ) (c_ {2,3} )
(c_ {4,3} ) (c_ {1,3} ) (c_ {2,3} ) (c_ {3,3} )
(c_ {1,1} ) (c_ {2,1} ) (c_ {3,1} ) (c_ {4,1} )
(c_ {2,1} ) (c_ {3,1} ) (c_ {4,1} ) (c_ {1,1} )
(c_ {3,1} ) (c_ {4,1} ) (c_ {1,1} ) (c_ {2,1} )
(c_ {4,1} ) (c_ {1,1} ) (c_ {2,1} ) (c_ {3,1} )
(c_ {1,2} ) (c_ {2,2} ) (c_ {3,2} ) (c_ {4,2} )
(c_ {2,2} ) (c_ {3,2} ) (c_ {4,2} ) (c_ {1,2} )
(c_ {3,2} ) (c_ {4,2} ) (c_ {1,2} ) (c_ {2,2} )
(c_ {4,2} ) (c_ {1,2} ) (c_ {2,2} ) (c_ {3,2} )

Teorema 4.3.11

f (A ) y (B ) son cuadrados latinos, así que (A times B ).

Prueba

Considere dos símbolos (c_ {i, j} ) y (c_ {k, l} ) en la misma fila. Si las posiciones que contienen estos símbolos están en la misma copia de (A ), entonces (i not = k ), ya que (A ) es un cuadrado latino, por lo que los símbolos (c_ {i, j} ) y (c_ {k, l} ) son distintas. De lo contrario, (j not = l ), ya que (B ) es un cuadrado latino. El argumento es el mismo para las columnas.

(cuadrado)

Sorprendentemente, esta operación conserva ortogonalidad:

Teorema 4.3.12

Si (A_1 ) y (A_2 ) son cuadrados latinos de orden (m ), (B_1 ) y (B_2 ) son cuadrados latinos de orden (n ), (A_1 ) y (A_2 ) son ortogonales, y (B_1 ) y (B_2 ) son ortogonales, entonces (A_1 times B_1 ) es ortogonal a (A_1 times B_2 ).

Prueba

Denotamos el contenido de (A_i times B_i ) por (C_i (w, x, y, z) ), es decir, la entrada en la fila (w ) y la columna (x ) de la copia de (A_i ) que reemplazó la entrada en la fila (y ) y la columna (z ) de (B_i ), que denotamos (B_i (y, z) ). Usamos (A_i (w, x) ) para denotar la entrada en la fila (w ) y la columna (x ) de (A_i ).

Suponga que ((C_1 (w, x, y, z), C_2 (w, x, y, z)) = (C_1 (w ', x', y ', z'), C_2 (w ', x ', y', z ')) ), donde ((w, x, y, z) not = (w', x ', y', z ') ). Ya sea ((w, x) not = (w ', x') ) o ((y, z) not = (y ', z') ). Si es lo último, entonces ((B_1 (y, z), B_2 (y, z)) = (B_1 (y ', z'), B_2 (y ', z')) ), una contradicción, ya que (B_1 ) es ortogonal a (B_2 ). Por tanto, ((y, z) = (y ', z') ) y ((w, x) not = (w ', x') ). Pero esto implica que ((A_1 (w, x), A_2 (w, x)) = (A_1 (w ', x'), A_2 (w ', x')) ), una contradicción. Por tanto, (A_1 times B_1 ) es ortogonal a (A_1 times B_2 ).

(cuadrado)

Queremos construir cuadrados latinos ortogonales de orden (4k ). Escribe (4k = 2 ^ m cdot n ), donde (n ) es impar y (m ge 2 ). Sabemos que hay cuadrados latinos ortogonales de orden (n ), por teorema 4.3.9. Si hay cuadrados latinos ortogonales de orden (2 ^ m ), entonces por teorema 4.3.12 podemos construir cuadrados latinos ortogonales de orden (4k = 2 ^ m cdot n ).

Para obtener un cuadrado latino de orden (2 ^ m ), también usamos el teorema 4.3.12. Basta encontrar dos cuadrados latinos ortogonales de orden (4 = 2 ^ 2 ) y dos de orden (8 = 2 ^ 3 ). Luego, aplicación repetida del teorema 4.3.12 nos permite construir cuadrados latinos ortogonales de orden (2 ^ m ), (m ge 2 ).

Dos cuadrados latinos ortogonales de orden 4:

$$ left [ matrix {1 & 2 & 3 & 4 cr 2 & 1 & 4 & 3 cr 3 & 4 & 1 & 2 cr 4 & 3 & 2 & 1 cr} right] left [ matrix {1 & 2 & 3 & 4 cr 3 & 4 & 1 & 2 cr 4 & 3 & 2 & 1 cr 2 & 1 & 4 & 3 cr} right], $$

y dos de orden 8:

$$ left [ matriz {1 y 3 y 4 y 5 y 6 y 7 y 8 y 2 cr 5 y 2 y 7 y 1 y 8 y 4 y 6 y 3 cr 6 y 4 y 3 y 8 y 1 y 2 y 5 y 7 cr 7 y 8 y 5 y 4 y 2 y 1 y 3 y 6 cr 8 y 7 y 2 y 6 y 5 y 3 y 1 y 4 cr 2 y 5 y 8 y 3 y 7 y 6 y 4 y 1 cr 3 y 1 y 6 y 2 y 4 y 8 y 7 y 5 cr 4 y 6 y 1 y 7 y 3 y 5 y 2 y 8 cr} right] left [ matriz {1 y 4 y 5 y 6 y 7 y 8 y 2 y 3 cr 8 y 2 y 6 y 5 y 3 y 1 y 4 y 7 cr 2 y 8 y 3 y 7 y 6 y 4 y 1 y 5 cr 3 & 6 & 2 & 4 & 8 & 7 & 5 & 1 cr 4 & 1 & 7 & 3 & 5 & 2 & 8 & 6 cr 5 & 7 & 1 & 8 & 4 & 6 & 3 & 2 cr 6 & 3 & 8 & 1 & 2 & 5 & 7 & 4 cr 7 & 5 & 4 & 2 & 1 & 3 & 6 & 8 cr} right]. $$


Los cuadrados latinos 4x4 y los patrones alfabéticos

La alfombra mágica fundamental de 4x4 se puede representar mediante puntos y espacios. Cualquier línea en cualquier dirección de longitud cuatro contiene dos puntos, es decir, suma a 2 cualquier área 4x4 seleccionada es un patrón pan-mágico. Podemos tomar cuatro muestras de esta gran alfombra, rotar dos de ellas y hacer las únicas cuatro posibles para ordenar cuatro alfombras mágicas.

Sustitución alfabética.

Debido a que se parecen un poco a las letras del alfabeto, se les da una letra para identificarlas.

La alfombra mágica alfabética compuesta

El punto en cada uno de los cuadrados anteriores se reemplaza con su propia letra. Luego, los cuatro cuadrados se combinan para hacer el cuadrado compuesto a la izquierda y luego la alfombra más grande a la derecha.

Solo existe un patrón compuesto. Este cuadrado compuesto subyace a todos los cuadrados pan-mágicos de orden 4. Cualquier área de 4x4 contiene cada letra dos veces en cada fila, cada línea y cada diagonal. Para hacer un cuadrado mágico de 4x4 real, las letras de este cuadrado se reemplazarían, respectivamente, por 8, 4, 2 y 1 (consulte la página principal de 4x4).

Patrón ordenado.

Cuando se repite el patrón, surge una gran alfombra mágica, agradable y simétrica, que crea el interesante patrón de colores de la izquierda.

No es una plaza latina

Estrictamente hablando, esto no es un "Cuadrado Latino". Un cuadrado latino para el orden N usa N letras N veces y cada fila y cada columna contiene una de cada letra. El cuadrado de arriba se puede convertir en dos cuadrados latinos.

Dos plazas latinas 4x4

La siguiente ilustración combina dos cuadrados latinos de 4x4 en un solo cuadrado, llamado greco-latino. Para mayor comodidad, emplea letras romanas mayúsculas y minúsculas en lugar de usar caracteres tanto romanos como griegos. Las letras del nuevo cuadrado se derivan del cuadrado de arriba:

A cuando ni S ni N están presentes
B cuando N está presente
C cuando S está presente
D cuando están presentes tanto S como N
a cuando ni C ni A están presentes
b cuando C está presente
c cuando A está presente
d cuando tanto C como A están presentes

A B C D
C D A B
B A D C
D C B A
+
a D C B
D a B C
B C D a
C B a D
=
Automóvil club británico Bd Cc Db
CD Da Ab Antes de Cristo
Cama y desayuno C.A Dd California
Corriente continua Cb Licenciado en Letras Anuncio

No Pan-Magic.

La inspección del grecolatino resultante muestra que las filas y columnas son inevitablemente "mágicas", contienen una de cada letra. Sin embargo, esto no es cierto para ninguna de las diagonales, solo se pueden sumar a la suma mágica para sustituciones numéricas seleccionadas apropiadamente.

Valor limitado para 4x4 Latin Squares.

Debido a esta limitación, los Latin Squares tienen un uso limitado en la construcción de cuadrados pan-mágicos 4x4. Hay otros dos posibles cuadrados alfabéticos de 4x4 y los tres se muestran a continuación. La tercera ni siquiera es latina en que, ahora, solo las diagonales contienen una de cada letra.


Versiones alternativas de ortogonalidad

(f) Cuadrados latinos parciales mutuamente ortogonales

Dos cuadrados latinos parciales (no necesariamente distintos) son ortogonal si, cuando se yuxtaponen, ningún par ordenado de elementos aparece más de una vez. Una colección de cuadrados latinos parciales se llama compatible con r si cada uno tiene r celdas ocupadas y estas celdas ocupadas están en posiciones correspondientes.

De ello se deduce que, en particular, un cuadrado latino parcial de orden norte que tiene solo norte de sus celdas ocupadas es ortogonal ay norte-compatible consigo mismo. Por tanto, la mayor parte del interés está en norte × norte cuadrados latinos que tienen más de norte células llenas. Este concepto, que se debe a Abdel-Ghaffar (1996), surgió en relación con la teoría de la codificación: es decir, al minimizar el tiempo de recuperación de elementos pertenecientes a un gran archivo de datos almacenados en varios discos.

Dejar METROnorte(r) denotan el número máximo de pares ortogonales r-Cuadrados latinos parciales compatibles. Para la aplicación anterior, Abdel-Ghaffar estaba interesado en encontrar límites para METROnorte(r) Cuándo r & gt norte. Demostró que, por norte + 1 ≤ rnorte 2 ,

Tenga en cuenta que este resultado implica en particular que METROnorte(norte 2 ) ≤ norte - 1. Abdel-Ghaffar demostró además que, por norte +1 ≤ r ≤ 2norte, METROnorte(r) = ⌊r(r − 1)/2(rnorte) ⌋ - 2 y construyó cuadrados que se encuentran con el último límite.

En la aplicación de la teoría de codificación mencionada anteriormente, los límites anteriores en METROnorte(r) dan límites al mejor tiempo de recuperación posible.


4.4: Cuadrados latinos - Matemáticas

Como recordatorio, debemos mencionar aquí que el pedido de un cuadrado mágico es el número de celdas en uno de sus lados.

Recuerde que el primer cuadrado mágico de cuarto orden registrado parece haber sido encontrado en una inscripción en Khajuraho, India que data de aproximadamente 1000-1100 d.C. Era de la forma

Examinaremos un método para crear un cuadrado mágico 44; sin embargo, este método no genera el cuadrado que se encuentra en la India. (Esta no es la única forma, pero es rápida y segura). Comenzamos creando una matriz de 44 cuadrados y luego dibujamos dos líneas diagonales para obtener una figura de la siguiente manera.


Luego comenzamos en la esquina superior izquierda para poner el número 1,2,3. 14,15,16 en las celdas. Sin embargo, no colocamos un número en ninguna celda donde aparece la línea diagonal. Comenzamos con 1, pero esa celda tiene una línea diagonal, así que vamos a la siguiente celda que está en blanco e ingresamos un 2, luego colocamos un 3 en la siguiente celda. La última celda de la primera fila tiene una línea diagonal, por lo que no escribimos en el 4. Vamos a la siguiente fila e ingresamos 5 en la primera celda, que está en blanco, las dos siguientes celdas tienen una línea diagonal, por lo que saltar 6 y 7. Continuamos este patrón hasta llegar a la última celda de la última fila. Nuestro cuadrado se verá así:

Ahora comenzamos en la esquina inferior derecha y regresamos usando los números 1, 4, 6, 7, 10, 11, 13 y 16. Ponemos estos números en las celdas que originalmente tenían las líneas diagonales que comienzan con 1 en la esquina inferior derecha. Nuestro producto terminado se ve así:

Vemos que en nuestro cuadrado terminado cada fila, columna y diagonal suma el número mágico 34, que se encuentra, como mencionamos anteriormente, calculando 4 (4 2 + 1) / 2.

Una vez que tengamos este cuadrado, podemos con cuidado reorganiza las filas y columnas para obtener otros 44 cuadrados mágicos. A continuación se muestran algunas reordenaciones de nuestro 44 cuadrado mágico original.

Observe en el reordenamiento que los números en nuestro 44 cuadrado mágico original permanecen juntos. Es decir, los números 16,2,3,13 que aparecen en la primera fila siempre estarán juntos, en algún orden, en una fila o columna de un nuevo cuadrado. Esto es cierto para todos los otros conjuntos de cuatro números. Por ejemplo, si tiene una fila o columna que contiene los números 3 y 6, esa fila o columna también debe tener los números 10 y 15.

En nuestros ejemplos reorganizados anteriores, el último cuadrado mágico tiene un interés histórico particular en las matemáticas y el arte. Este cuadrado mágico aparece en el fondo del grabado. Melencolia por Albrecht D & uumlrer, lo que hizo en 1514. Observe que los números 15 y 14 (la fecha del grabado) aparecen juntos en el centro de la fila inferior. Este grabado se puede ver en muchos lugares. Uno conveniente es el WebMuseum. Si este enlace no lo lleva allí, intente con la puerta principal. El principal punto de entrada al WebMuseum es Pyramide.


Ejercicios 4.3

Ej 4.3.1 Muestre que solo hay un cuadrado latino reducido de orden 3.

Ej 4.3.2 Verifique que la relación de isotopía sea una relación de equivalencia.

Ej 4.3.3 Encuentre los 4 cuadrados latinos reducidos de orden 4. Demuestre que hay como máximo 2 clases de isotopías para el orden 4.

Ej 4.3.4 Muestre que el segundo sistema de conjuntos definido en el ejemplo 4.3.7 tiene un DEG como se afirma.

Ej 4.3.5 Demuestre que no hay cuadrados latinos ortogonales de orden 2.

Ej 4.3.6 Encuentre los dos cuadrados latinos ortogonales de orden $ 5 $ como se describe en el teorema 4.3.9. Muestre su respuesta como en el ejemplo 4.3.10.

Ej 4.3.7 Demuestre que para construir cuadrados latinos ortogonales de orden $ 2 ^ m $, $ m ge2 $, basta con encontrar dos cuadrados latinos ortogonales de orden $ 4 = 2 ^ 2 $ y dos de orden $ 8 = 2 ^ 3 $.

Ej 4.3.8 Un $ n times n $ cuadrado latino $ A $ es simétrico si es simétrico alrededor de la diagonal principal, es decir, $ A_= A_$ para todos los $ i $ y $ j $. Es fácil encontrar cuadrados latinos simétricos: cada tabla de suma módulo $ n $ es un ejemplo, como en el ejemplo 4.3.6. Un cuadrado latino es idempotente si cada símbolo aparece en la diagonal principal. Demuestre que si $ A $ es simétrico e idempotente, entonces $ n $ es impar. Encuentre un cuadrado latino idempotente simétrico de $ 5 times 5 $.

Ej 4.3.9 La transponer $ A ^ top $ de un cuadrado latino $ A $ es el reflejo de $ A $ en la diagonal principal, de modo que $ A_^ top = A_PS Un cuadrado latino es auto-ortogonal si $ A $ es ortogonal a $ A ^ top $. Demuestre que no existe un cuadrado latino auto-ortogonal de orden 3. Encuentre uno de orden 4.


Investigadores en teoría del diseño combinatorio y áreas de la estadística como diseño y análisis de experimentos. El libro también puede ser de interés para los matemáticos aficionados interesados ​​en los cuadrados mágicos, en el diseño de juegos de torneos y / o en los cuadrados latinos relacionados con los Sudoku.

Capítulo 1: Propiedades elementales

  • 1.1 La tabla de multiplicar de un cuasigrupo
  • 1.2 La mesa Cayley de un grupo
  • 1.3 Isotopía
  • 1.4 Conjugado y parastrofia
  • 1.5 Transversales y mapeos completos
  • 1.6 subcuasigrupos y subcuasigrupos latinos

Capítulo 2: Tipos especiales de cuadrado latino

  • 2.1 Identidades de cuasigrupos y cuadrados latinos
  • 2.2 Cuasigrupos de algunos tipos especiales y el concepto de asociatividad generalizada
  • 2.3 Sistemas triples y cuasigrupos
  • 2.4 Cuadrados latinos basados ​​en grupos y núcleos de bucles
  • 2.5 Transversales en cuadrados latinos basados ​​en grupos
  • 2.6 Cuadrados latinos completos

Capítulo 3: Cuadrados latinos parciales y transversales parciales

  • 3.1 Rectángulos latinos y cuadrados latinos en fila
  • 3.2 Conjuntos críticos y Sudoku
  • 3.3 Problemas de Fuchs
  • 3.4 Cuadrados latinos incompletos y cuasigrupos parciales
  • 3.5 Transversales parciales y transversales generalizadas

Capítulo 4: Clasificación y enumeración de cuadrados latinos y rectángulos latinos

  • 4.1 El grupo de autotopismo de un cuasigrupo
  • 4.2 Clasificación de cuadrados latinos
  • 4.3 Historia de la clasificación y enumeración de cuadrados latinos
  • 4.4 Enumeración de rectángulos latinos
  • 4.5 Enumeración de transversales
  • 4.6 Enumeración de subcuadradas

Capítulo 5: El concepto de ortogonalidad

  • 5.1 Preguntas de existencia para conjuntos incompletos de cuadrados latinos ortogonales
  • 5.2 Conjuntos completos de cuadrados latinos ortogonales y planos proyectivos
  • 5.3 Juegos de MOLS de tamaño máximo y mínimo
  • 5.4 Cuasigrupos ortogonales, grupoides y sistemas triples
  • 5.5 Cuadrados y cuasigrupos latinos ortogonales auto-ortogonales y otros parastróficos
  • 5.6 Ortogonalidad en otras estructuras relacionadas con los cuadrados latinos

Capítulo 6: Conexiones entre cuadrados latinos y cuadrados mágicos

  • 6.1 Cuadrados latinos diagonales (o mágicos)
  • 6.2 Construcción de cuadrados mágicos con la ayuda de cuadrados latinos ortogonales
  • 6.3 Resultados adicionales en cuadrados mágicos
  • 6.4 Cuadrados de habitaciones: su construcción y usos

Capítulo 7: Construcciones de cuadrados latinos ortogonales que implican el reordenamiento de filas y columnas.


Sección del caso 3

En este caso, tenemos diferentes niveles de factores de fila y columna. Nuevamente, en nuestro escenario de fábrica, tendríamos diferentes máquinas y diferentes operadores en las tres réplicas. En otras palabras, ambos factores estarían anidados dentro de las réplicas del experimento.

Escribiríamos este modelo como:

Aquí hemos utilizado términos anidados para ambos factores de bloque que representan el hecho de que los niveles de estos factores no son los mismos en cada una de las réplicas.

La tabla de análisis de varianza incluiría:


Cualquier cosa menos cuadrado: desde cuadrados mágicos hasta Sudoku

Hay una antigua leyenda china que dice algo así. Hace unos tres mil años, ocurrió una gran inundación en China. Para calmar al afligido dios del río, la gente hizo una ofrenda al río Lo, pero no pudo ser apaciguado. Cada vez que hacían una ofrenda, aparecía una tortuga del río. Un día, un niño notó marcas en el dorso de la tortuga que parecían representar los números del 1 al 9. Los números estaban dispuestos de tal manera que cada línea sumaba 15. Por lo tanto, la gente entendió que su ofrenda no era cantidad correcta.

Las marcas en la espalda de la tortuga eran de hecho un cuadrado mágico. Un cuadrado mágico es una cuadrícula llena de números, de tal manera que cada fila, cada columna y las dos diagonales suman el mismo número. Así es como se vería el cuadrado mágico de Lo Shu. Tiene tres filas y tres columnas, y si suma los números en cualquier fila, columna o diagonal, siempre obtiene & # 13 15.

Aquí hay una construcción parcial de un cuadrado mágico de 5 por 5. A partir del 1, he completado los números hasta el 10. No hay espacio al noreste del 1, por lo que he puesto el 2 en la fila inferior, seguido del 3. Nuevamente, debido a que el 3 está en el borde, el 4 va en el lado opuesto. El 6 debería ir en la celda donde está el 1, pero debido a que esta celda está ocupada, puse el 6 inmediatamente debajo del 5 & # 13 y continué hasta el 10. Intente completar el cuadrado y luego intente hacer uno propio.

Si bien esto, conocido como el Método siamés, es probablemente el método más conocido para hacer cuadrados mágicos, existen otros métodos. El maestro de escuela alemán Johann Faulhaber publicó un método similar al método siamés antes de que fuera descubierto por De Le Loubere. Otra forma es la Método de pastilla por John & # 13 Horton Conway, un prolífico matemático británico. Demostrar que estos métodos funcionan se puede hacer usando álgebra, ¡pero no es fácil!

Cuadrados mágicos de orden uniforme

Aunque el método siamés se puede utilizar para generar un cuadrado mágico para cualquier número impar, no existe un método simple que funcione para todos los cuadrados mágicos de orden par. Afortunadamente, existe un buen método que podemos usar si el orden del cuadrado es un número par divisible por 4. (Para aquellos que estén interesados, el Método LUX fue inventado por J. H. Conway para tratar con números pares que no son divisibles por 4).

En lugar de decir "números divisibles por 4", los matemáticos suelen decir "números de la forma 4k". Por ejemplo, 12 tiene el formato 4k, porque puedes reemplazar k con 3. Usando la misma idea, los números que dan un resto de 2 cuando los divides entre 4 pueden llamarse números de la forma 4k + 2.

Así que empieza eligiendo el orden del cuadrado, asegurándote de que tenga la forma 4ky numera las celdas 1 a (4k) 2 comenzando en la parte superior izquierda y trabajando a lo largo de las filas. Luego divide el cuadrado en 4 por 4 subcuadrados y marca los números que se encuentran en las diagonales principales de cada subcuadrado. En el ejemplo, estos son los números de colores, el orden del cuadrado es & # 13 4, por lo que el único subcuadrado de 4 por 4 es el propio cuadrado.

Ahora cambie el número marcado más bajo con el número marcado más alto, el segundo número marcado más bajo con el segundo número marcado más alto, y así sucesivamente. Otra forma de decir esto es que si el cuadrado mágico tiene orden norte, intercambia los números que suman n 2 + 1. En este ejemplo en particular, el orden es 4, por lo que tenemos que intercambiar los números que suman 17: 1 y 16, 4 y 13, & # 13 6 y 11, 7 y 10.

Si le das la vuelta a este cuadrado mágico, es idéntico al dibujado por el famoso artista alemán Alberto Durero. Puedes verlo en la esquina de su grabado. Melencolia.

Un cuento de caballeros

Como sabrá cualquier jugador de ajedrez, un cuadrado mágico de orden 8 tiene el mismo número de celdas que un tablero de ajedrez. Esta similitud significa que podemos crear un tipo especial de cuadrado mágico basado en los movimientos de una pieza de ajedrez.

El caballo es una pieza interesante, porque a diferencia de las otras piezas, no se mueve vertical, horizontal o diagonalmente a lo largo de una línea recta. En cambio, el caballo se mueve en forma de L como se muestra en el diagrama. Pero, ¿es posible que un caballo que se mueve de esta manera visite cada casilla del tablero de ajedrez exactamente una vez?

Usando el concepto de la gira de los caballeros, William Beverley logró producir un cuadrado mágico, como se muestra a continuación. Las celdas se numeran en secuencia, a medida que el caballero las visita. Aunque las filas y columnas suman 260, las diagonales principales no, por lo que estrictamente hablando es un cuadrado semimágico. De hecho, un cuadrado mágico basado en el recorrido de un caballero a menudo se denomina recorrido mágico, por lo que lo que Beverley produjo en 1848 es un recorrido semimágico.

A primera vista, parece que el siguiente cuadrado mágico de Feisthamel encaja perfectamente. Las filas, columnas y diagonales suman 260. Desafortunadamente, es solo un recorrido parcial de caballeros, ya que hay un salto de 32 a 33.

Entonces, ¿cuándo es posible convertir la gira de un caballero en un cuadrado mágico? En 2003, Stertenbrink y Meyrignac finalmente resolvieron este problema calculando todas las combinaciones posibles. Encontraron 140 recorridos semi-mágicos, pero no recorridos mágicos. ¡Mate!

Cuadrados latinos

Los cuadrados latinos son los verdaderos ancestros del Sudoku. Puede encontrar ejemplos de cuadrados latinos en la literatura árabe de más de 700 años. Fueron descubiertos por Euler unos siglos después, quien los vio como un nuevo tipo de cuadrado mágico, y es gracias a él que los llamamos cuadrados latinos.

Los cuadrados latinos son cuadrículas llenas de números, letras o símbolos, de tal manera que ningún número aparece dos veces en la misma fila o columna. La diferencia entre un cuadrado mágico y un cuadrado latino es la cantidad de símbolos utilizados. Por ejemplo, hay 16 números diferentes en un cuadrado mágico de 4 por 4, pero solo necesitas 4 números o letras diferentes para hacer un cuadrado latino de 4 por 4.

Ahora, si miramos los tres cuadros inferiores, una de las filas ya tiene 6 números. He llamado a las celdas vacías A, B y C (en orden de izquierda a derecha), y los números que faltan son 3, 7 y 8. Si miras la celda C, el único número que puede entrar es 7. Eso es porque la columna en la que se encuentra C ya contiene 3 y 8.

Encontrar A y B ahora es bastante simple. Ya hay un 3 en la misma columna que B, por lo que B tiene que ser 8. Eso significa que A debe ser 3. Resolver el resto del rompecabezas es un poco más complicado, pero vale la pena el esfuerzo.

La locura del Sudoku se ha extendido por todo el mundo y no muestra signos de desaceleración. Se han desarrollado varias variaciones a partir del tema básico, como versiones de 16 por 16 y combinaciones de cuadrículas múltiples (puede probar una diferencia dúplex sudoku en el Más rompecabezas). Pero al igual que con los cuadrados mágicos y los cuadrados latinos, la popularidad del Sudoku dependerá de si pueden continuar ofreciendo nuevos desafíos.


Diseño de cuadrados latinos

En esta página web, describimos los conceptos básicos de los diseños de Latin Squares. Puede encontrar información adicional en las siguientes páginas web:

A Plaza Latina El diseño tiene dos factores de molestia (filas y columnas) y un factor de tratamiento, cada uno de los cuales tiene el mismo número de niveles, denotados r. No hay réplicas ni interacciones. Si denotamos los posibles efectos del tratamiento con letras latinas, entonces todas las filas y columnas son permutaciones de estas letras (sin filas repetidas ni columnas repetidas).

Para r = 4 y r = 5, las posibles configuraciones son:

Figura 1 - Configuraciones de Latin Square

Tenga en cuenta que hay muchas configuraciones posibles de 4 × 4 o más grandes, aunque muchas de ellas son equivalentes en el sentido de que se puede obtener una de otra intercambiando una o más filas y / o columnas. De hecho, hay 4 configuraciones 4 × 4 no equivalentes y 56 configuraciones 5 × 5 no equivalentes. Resulta que todas las configuraciones de 3 × 3 son equivalentes.

Ejemplo 1: Una fábrica desea determinar si existe una diferencia significativa entre cuatro métodos diferentes de fabricación de un componente de avión, basándose en la cantidad de milímetros de la pieza a partir de la medida estándar. Se asignan al estudio cuatro operadores y cuatro máquinas. Se utiliza un diseño de Latin Squares para tener en cuenta los factores de molestia de los operadores y las máquinas.

La representación de un diseño de Latin Squares se muestra en la Figura 2 donde A, B, C y D son los cuatro métodos de fabricación y las filas corresponden a los operadores y las columnas corresponden a las máquinas.

Figura 2 - Representación de cuadrados latinos

Para nuestros propósitos, usaremos las siguientes representaciones equivalentes (ver Figura 3):

Figura 3 - Diseño de cuadrados latinos

The linear model of the Latin Squares design takes the form:

An Excel implementation of the design is shown in Figure 4.

Figure 4 – Latin Square Analysis

The left side of Figure 4 contains the data range in Excel format (equivalent to the left side of Figure 3). The middle part of Figure 4 contains the means of each of the factor levels. Representative formulas used are shown in Figure 5.

Cell Factor Fórmula
L4 Row =AVERAGE(H4:K4)
H8 Column =AVERAGE(H4:H7)
H11 Treatment =AVERAGEIF($B$8:$E$11,H10,$B$4:$E$7)

Figure 5 – Formulas for factor means

The right side of Figure 4 contains the ANOVA analysis. The degrees of freedom for all three factors is 3 (cells P4, P5, P6), equal to the number to r – 1, as calculated by =COUNT(B4:B7)-1. dfT = r 2 – 1 = 15, while dfmi = (r–1)(r–2) = 6.

Formulas for the sum of squares (SS) terms are shown in Figure 6. The other values in Figure 4 are calculated in the usual way.

Cell Factor Fórmula
O5 Treatment =DEVSQ(H11:K11)*(P5+1)
O6 Rows =DEVSQ(L4:L7)*(P6+1)
O7 Columns =DEVSQ(H8:K8)*(P7+1)
O8 Error =O9-SUM(O5:O7)
O9 Total =DEVSQ(H4:K7)

Figure 6 – Formulas for sums of squares

We see from Figure 4 that there is a significant difference between the four methods (p-value = 0.03345 < .04 = α). There is no significant difference between the operators or between the machines, and so blocking on these factors may not have been necessary in this case.

The analysis is similar when the standard (i.e. stacked) input format is used (see Figure 7). E.g. the mean for row 1 (cell G4) can be calculated by the formula

The mean for treatment A (cell I4) can be calculated by using the formula

Figure 7 – Latin Square Analysis for stacked format

Observation: In the usual three-factor design, the minimum sample size would be 4 × 4 × 4 = 64, while in this design we only require a sample size of 4 × 4 = 16.

Observation: Latin Squares can also be used for a three-factor ANOVA when there are no replications, even when the row and column factors are not nuisance factors, but factors of interest.


Disclaimer

Registration on or use of this site constitutes acceptance of our User Agreement, Privacy Policy and Cookie Statement, and Your California Privacy Rights (User Agreement updated 1/1/21. Privacy Policy and Cookie Statement updated 5/1/2021).

© 2021 Advance Local Media LLC. All rights reserved (About Us).
The material on this site may not be reproduced, distributed, transmitted, cached or otherwise used, except with the prior written permission of Advance Local.

Community Rules apply to all content you upload or otherwise submit to this site.


Latin Square in C++

In this tutorial, we are going to learn about the Latin square.

The latin square is a matrix (3 x 3) in the form

If you carefully observe the pattern of the above matrix, then you will find out that the last number of the previous row comes as the first element of the next row.

We have to write the program that generates the above matrix for the input n.

Let's see the steps to write the program for the generation of the latin square.

  • Initialise the n with any number you like.
  • Initialise a number with the value n + 1 call it as mid.
  • Write a loop that iterates from 1 to n both inclusive.
    • Assign the value of mid to a temp variable.
    • Write a loop until temp reaches to the value n.
      • Print the temp.
      • Print the value.

      If you run the above code, then you will get the following result.


      Ver el vídeo: Ejercicio de Diseño de Cuadro latino y Grecolatino en minitab. (Septiembre 2021).