Plaza grecolatina
Un cuadrado grecolatino o cuadrado euleriano de orden n , sobre dos conjuntos G y L de cada n símbolos, es una matriz cuadrada de n filas yn columnas, que contiene las n 2 parejas de L × G , y donde cualquier fila y cada La columna contiene exactamente una vez cada elemento de L (en la primera posición en uno de los n pares) y cada elemento de G (en la segunda posición). Es la superposición de dos cuadrados latinos ortogonales entre sí. También decimos “cuadrado de bilatina”.
El nombre “greco-latino” proviene del hecho de que a menudo usamos para G y L el comienzo de los alfabetos griego y latino .
Ejemplos de
Dos cuadrados latinos ortogonales
Considere los siguientes dos cuadrados latinos de orden 4, en los conjuntos L = { A , B , C , D } y G = {α, β, γ, δ}:
Su superposición (opuesta) es un cuadrado grecolatino porque no se repite ningún par de L × G (por lo tanto, cada par aparece una vez y solo una vez): decimos que los dos cuadrados latinos son ortogonales.
Dos cuadrados latinos no ortogonales
Reemplacemos el segundo de los dos cuadrados latinos anteriores con lo siguiente:
Ya no es ortogonal al primero, es decir que su superposición no da un cuadrado grecolatino:
De hecho, notamos que cuatro parejas aparecen dos veces (y que cuatro están ausentes).
Historia
Primeros frutos
Una edición póstuma ( 1725 ) de Recreaciones matemáticas et physique de Jacques Ozanam propone (vol. 4, p. 434 ) construir un cuadrado grecolatino de orden 4, en un rompecabezas formulado en términos de naipes : el problema es tomar todos los ases , reyes , reinas y jotas de un juego estándar y organizarlos en una cuadrícula de 4 × 4 de modo que cada fila y cada columna contenga los cuatro signos ( tréboles ♣ , diamante ♦ , corazones ♥ , espadas ♠ ) y los cuatro valores . Hay varias soluciones.
El trabajo de Euler y sus dos conjeturas
En 1779 , el matemático suizo Leonhard Euler definió y estudió en detalle los cuadrados grecolatinos de orden n , sobre los alfabetos griego y latino y luego sobre enteros estrictamente positivos . Produce métodos para construir algo si n es impar o un múltiplo de 4. Por lo tanto, queda por tratar el caso donde n es congruente con 2 módulo 4 . Observa que no hay un cuadrado grecolatino de orden 2 e ilustra el orden 6 por su "problema de 36 oficiales":
“36 Oficiales de seis rangos diferentes y extraídos de seis regimientos diferentes, que debían estar dispuestos en un cuadrado, de modo que en cada línea, tanto horizontal como vertical, hubiera seis oficiales de diferente carácter y de diferentes regimientos. "
Él conjeturas que este problema no tiene solución:
“Ahora, después de todos los esfuerzos que nos hemos tomado para resolver este Problema, nos hemos visto obligados a reconocer que tal arreglo es absolutamente imposible, aunque no podemos dar una demostración rigurosa de ello. "
e incluso que, de manera más general, para cualquier n congruente con 2 módulo 4, no existe un cuadrado grecolatino de orden n :
“He examinado por este método un número muy grande de cuadrados […] y no he dudado en concluir, que no se podría producir un cuadrado completo de 36 cuadrados, y que la misma imposibilidad se extiende para los casos de n = 10, n = 14 y en general para todos los números pares impares. "
Primera conjetura confirmada y segunda refutada
En 1842 , gracias a una búsqueda exhaustiva de los casos y cruzando los resultados, el danés Thomas Clausen logra, con toda probabilidad, demostrar la primera conjetura de Euler: no hay un cuadrado grecolatino de orden 6. Pero su demostración tiene no nos ha llegado. La primera prueba publicada, que sigue el mismo método, se debe al francés Gaston Tarry , en 1901.
En 1.959 mil - 1.96 mil , Bose , Parker (en) y Shrikhande invalida completamente la segunda: aparte de las dos excepciones ya conocidos ( n = 2 y n = 6), existen cuadrados grecolatinos de orden n para todo n ≡ 2 ( mod 4) por lo tanto finalmente: para todo n .
Aplicaciones
- Georges Perec estructuró su novela La Vie mode Emploi (publicada en 1978) en un cuadrado grecolatino de orden 10.
- Los cuadrados grecolatinos se utilizan en el diseño de experimentos y planificación de torneos.
- Algunos cuadrados grecolatinos te permiten construir ciertos cuadrados mágicos . Más precisamente: en un cuadrado grecolatino de orden n en G = L = {0, 1,…, n - 1}, reemplazando cada par ( x , y ) por el número nx + y , obtenemos un cuadrado hecho arriba de los números de 0 an 2 - 1, con la misma suma en cada fila y cada columna (pero no siempre en las dos diagonales, y a la inversa, un cuadrado mágico normal de orden n puede no originarse en un latín greco-cuadrado) .
Notas y referencias
- (en) Donald Knuth , El arte de la programación informática , vol. 4A, pág. 3 .
- L. Euler, Investigaciones sobre una nueva especie de cuadrados mágicos , E530 , presentado a la Academia de San Petersburgo el 8 de marzo de 1779. Sorprendentemente, este artículo de Euler está escrito en francés y es el único publicado en un periódico holandés. (en 1782).
- Euler, op. cit. , § 17.
- Euler, op. cit. , § 1.
- Euler, op. cit. , Párrafo 144.
- (en) Dominic Klyve y Lee Stemkoski, " Los cuadrados grecolatinos y tiene conjetura errónea de Euler " , Facultad de Matemáticas Diario (en) , vol. 37, n o 1,2006, p. 2-15 ( leer en línea ).
- G. Tarry, " El problema de los 36 oficiales (I) ", Actas de la Asociación francesa para el avance de la ciencia , vol. 1,1900, p. 122-123y G. Tarry, " (II) ", CR Assoc. Franco. Av. Sci. , vol. 2,1901, p. 170-203.