¿Cómo se resuelve el problema de 'los 36 oficiales'?

Recordemos que un cuadrado latino es una disposición cuadrada de símbolos (pueden ser letras, números, colores, dibujos, cualquier cosa) en el que cada uno no se repite nunca en la misma fila o columna. No hay ninguna operación aritmética (a diferencia de los cuadrados mágicos), simplemente se disponen los objetos de la manera descrita. Vuelvo a mostrar la misma imagen del artículo anterior, para que quede claro a qué nos referimos. Es un cuadrado latino de orden cuatro (hay cuatro filas y cuatro columnas) con números, y el mismo, con colores.

Seguramente hayan oído o leído alguna vez (es un ejemplo que se cita habitualmente) el problema de los 36 oficiales descrito por Leonhard Euler a finales del siglo XVIII (la fecha exacta no está clara: algunos autores señalan 1779, otros 1782, en fin, el dato tampoco nos importa mucho), planteado al matemático, según la leyenda, por la reina Catalina II (Catalina la Grande) durante su estancia en Rusia: ¿es posible disponer a treinta y seis oficiales de seis regimientos distintos y de cada uno de los seis grados, en un cuadrado de 6x6 de forma que no coincidan dos oficiales del mismo rango o del mismo regimiento en ninguna fila y en ninguna columna?

En realidad, el problema no era nuevo porque en el libro póstumo 'Recreation mathematiques et physiquese' (1725), el matemático francés Jacques Ozanam plantea disponer los ases, reyes, reinas y jacks de la baraja francesa en cuadrado 4x4 de modo que cada fila,

cada columna y las dos columnas no repitan ni palo ni carta. Lo mismo que planteaba Antonio Pomares con su cuadrado de Foz en el anterior artículo (y por eso comenté que esa parte no era novedosa sino perfectamente conocida). Una de las dos soluciones posibles es la mostrada arriba con colores. Por cierto, ningún lector me ha hecho llegar la otra posible configuración diferente, así que aquí se la pongo (recuerden que se entiende por configuración diferente aquella que se obtiene de otra ni por simetrías ni por giros). Probablemente Euler conocería estas configuraciones y por tanto que con 16 oficiales el acertijo estaba resuelto. Pero fue incapaz de resolver el de 6 x 6, es decir, el de los 36 oficiales, así que se puso a pensar la situación en general.

Es fácil ver que tampoco es posible resolver la situación para un cuadrado 2 x 2, de modo que conjeturó que no existe solución cuando el orden es un número par n ≡ 2 (mod 4) (Recordemos lo que significa 'ser congruente': n ≡ 2 (mod 4), quiere decir que n – 2 es un múltiplo de 4, o sea n no podía ser 2, 6, 10, 14, 16, 22, …). En resumen, que la disposición de n^2 oficiales con las condiciones descritas sólo era posible cuando n fuera impar o múltiplo de 4. Pero lo que tienen las conjeturas, no habiendo demostración alguna más que un par de casos particulares, es que pueden ser falsas. Afortunadamente Euler llevaba ya tiempo criando malvas cuando en 1959 los matemáticos indios Raj Chandra Bose y Sharadchandra Shankar Shrikhand e (como curiosidad, éste segundo murió el año pasado, ¡¡con 102 años!!) encontraron una solución para n = 22.

Unos años después, Ernest Tilden Parker encontró otro contraejemplo a la conjetura de Euler para n = 10 (aunque éste hizo trampa porque lo halló mediante una máquina UNIVAC 1206 : es uno de los primeros problemas combinatorios resueltos por una computadora). Ese contraejemplo lo podéis ver en la imagen adjunta.

Está formado por dos cuadrados latinos en realidad: si nos fijamos en los dígitos marcados en color rojo, cada fila y columna tiene todos, del 0 al 9, sin que se repita ninguno. Lo mismo sucede con los números en negro.

Posteriormente, los tres matemáticos trabajando ya juntos, demostraron que la solución al problema es posible para todo n mayor o igual que 10. En la portada de ' Scientific American ' de noviembre de 1959, se reprodujo una pintura al óleo de una de las dibujantes de la revista, Emi Kasai, en el que asignó un color a cada dígito del cuadrado 10 x 10 de la imagen anterior (por tanto 10 colores diferentes). En cada cuadrado, inscribe un cuadradito más pequeño. El color de éste corresponde a los dígitos en negro, y los rojos a los del espacio que queda hasta rellenar cada cuadrado completamente. Obsérvese que el 00 se encuentra en la esquina superior derecha, es decir, está girado respecto al cuadrado numérico. En el interior de la revista, Martin Gardner , dedicó al tema su columna mensual.

Como ven, los mayores genios de la humanidad son precisamente eso, humanos, y también se equivocan en ocasiones (por supuesto mucho menos que los charlatanes que nos rodean, aunque a esos les importa un bledo, obviamente, el errar). Afortunadamente no todo fueron malas noticias para el espíritu de Euler en caso de que tal ente exista, porque en 1901, el francés Gaston Tarry demostró que colocar los 36 oficiales (o sea el caso n = 6) era imposible, no existía solución. Concluyendo, los únicos cuadrados latinos imposibles de construir son los casos de orden 2 y 6. Para el resto de los infinitos números, existe solución. De modo que si quieren epatar a alguien (o simplemente gastarle una broma), ya saben lo que tienen que hacer: retarle a que construya un sudoku 6 x 6 con los seis primeros dígitos, a ver si es capaz.

Volviendo a los acertijos planteados (el de los oficiales y el de las cartas de la baraja), en ambos debemos compaginar dos condiciones. En uno el ejército y el rango, y en el otro, la carta y el palo al que pertenece. Podemos tratar de resolver la situación con una única condición, y después, por separado, con la otra, y ver si su unión, cuadra con que se cumplan ambas condiciones a la vez.

Por ejemplo, con las cartas, la primera condición (que no se repitan los valores de las cartas en filas, columnas y diagonales principales), podemos dar esta solución (basta con que, en el cuadrado de la primera imagen de arriba, la de los números, asignemos por ejemplo el 1 al As, el 2 al rey, el 3 al Jack, y el 4 a la reina. Tenemos así el siguiente cuadrado:

Buscamos ahora otro cuadrado que resuelva la situación de los palos. Por ejemplo, en el primero de los colores que pusimos arriba, identificando color rojo con picas, color azul con corazones, color amarillo con diamantes y color verde con tréboles, y superponiendo ambos cuadrados, obtenemos la solución buscada con sencillez, como vemos en la imagen.

A estos cuadrados que combinan dos cuadrados latinos y con cada condición respetan el hecho de que no se repita dicha condición en filas, columnas ni diagonales principales se le llama cuadrado greco-latino (el nombre viene de que uno de ellos puede escribirse con letras latinas, y el segundo con letras griegas). Cuando es posible esta combinación se dice que esos dos cuadrados son ortogonales.

Está demostrado que para orden n, existen como máximo n – 1 cuadrados ortogonales. Así pues, existen dos cuadrados ortogonales de orden 3, tres de orden 4, y así sucesivamente (salvo para n = 6, recuerden, que para ese orden no existe ningún cuadrado greco-latino). El conjunto de todos los cuadrados ortogonales para cada n, se le denomina familia completa. Pues bien, hasta n = 9 se conocen sus familias completas, pero a partir de n = 10 no. Fíjense que el cuadrado greco-latino de orden 10 que mostramos anteriormente, está formado por la unión de dos sudokus de los que vienen en los periódicos (por un lado, el formado por los dígitos en color rojo, y por otro, los marcados en negro). Esos dos son ortogonales porque se combinan perfectamente (la condición de las diagonales no la verifican). La familia completa estará formada por un total de 9 cuadrados latinos ortogonales diferentes. ¿Saben cuántos posibles sudokus diferentes se pueden formar? Se lo digo:

6.670.903.752.021.072.936.960

O sea, del orden de 6.67 x 10^21. Pues bien, se sabe que 9 de ellos como máximo son ortogonales, pero aún no se han encontrado. ¿Se animan a buscarlos?

Por cierto, para los que piensen que han hecho muchos sudokus, y a lo mejor ya los han hecho todos. Si resolvieran un sudoku por minuto las veinticuatro horas del día (todos distintos), y se dedicaran a ello los próximos cien años sin parar, no resolverían ni siquiera un 1% del total de los posibles. De modo que, tranquilos, que tiene pasatiempo para rato.

Existen diferentes algoritmos para obtener cuadrados mágicos (recuerden: sumas de cada fila, columna o diagonales principales igual) a partir de cuadrados greco-latinos (Euler utilizaba procedimientos de este tipo). Explicamos uno de ellos. Pasemos a valores numéricos el cuadrado greco-latino de la última imagen de la baraja francesa (recordemos que son dos cuadrados latinos ortogonales), siendo A el 0, K el 1, Q el 3 y J el 2. Del segundo cuadrado latino (el de los palos), las picas el 0, los corazones el 1, los diamantes el 2 y los tréboles el 3. Con esas identificaciones se tiene la siguiente estructura:

Si cada uno de esos pares es (x, y), vamos a asignar a cada par el número que se obtiene al hacer la operación

n x + y

donde n es el orden del cuadrado mágico, en este caso, 4. Se obtiene entonces el cuadrado:

¡¡Oh, magia, magia!! Todas las filas, columnas y la diagonal suman lo mismo. ¿Cómo es posible? (Espero que haya alguien que me mande por qué sucede esto, sin aludir a la magia). ¿Qué quieren que sean los números del 1 al 16, y no del 0 al 15? Sin problema: sumen una unidad a todos los números, y lo tienen.

Terminemos indicando alguna aplicación más mundana de los cuadrados latinos y greco-latinos, más allá de los pasatiempos, los acertijos o contar cuántos puede haber (ejercicios de combinatoria), porque seguro que alguno de ustedes (o muchos) están pensando que los matemáticos nos lo pasamos genial con este tipo de 'empanadas mentales'. Pues miren no; recuerden siempre: un matemático nunca va a perder el tiempo en pensar en algo que no sirva para nada, porque para eso, es mejor no hacer nada (máxima que me acabo de inventar, pero que cuadra perfectamente conmigo, y con todos los que conozco).

Una aplicación muy famosa que les indico por si la leen por ahí, fue la de averiguar la eficacia de varios fertilizantes en el rendimiento de las cosechas para que la calidad de la tierra no sea un factor determinante e indeseable. Al estadístico y biólogo británico Ronald Aylmer Fisher se le planteó dicha cuestión en los años treinta del siglo pasado (si tienen un rato, lean algo sobre este científico porque su contribución a la biología y a la medicina fue sencillamente espectacular; y utilizando modelos matemáticos y estadísticos, por cierto). Imaginemos que tenemos n fertilizantes diferentes, y queremos contrastar su eficacia.

Evidentemente es inútil utilizar una tierra diferente para cada fertilizante, porque así no sabremos perfectamente la incidencia de cada uno, y tampoco podemos esperar años para probar un fertilizante por año en cada tipo de tierra. Lo que hizo Fisher fue dividir cada tierra en pequeñas parcelas (un cuadrado latino n x n), de modo que en cada fila y columna aplicó un fertilizante diferente, eliminando así el factor de la calidad de la tierra. Si de repente descubrimos que puede haber otro factor distinto a la calidad de la tierra que puede influir en la cosecha, por ejemplo, el momento del día en que se aplica, entonces consideramos un cuadrado greco-latino para introducir la segunda condición (es decir, buscar un cuadrado ortogonal al ya utilizado). Así conoceremos cuál es el mejor tratamiento del terreno y la zona horaria en el que esto sucede.

Detección, control y corrección de errores en señales digitales. Durante cualquier transmisión de información (audio, datos, imágenes) pueden aparecer interferencias, cortes de comunicación, errores del que transmite porque se ha despistado o tiene las gafas mal graduadas, en definitiva, alteraciones del mensaje original (lo que en términos técnicos se denomina 'ruido'). Se han desarrollado muchos procedimientos y algoritmos que tratan de paliar estas anomalías (hay toda una rama en las telecomunicaciones que se dedica a ello, la teoría de la señal). Para mejorar las posibilidades de una buena transmisión, se suelen añadir al mensaje caracteres redundantes, de forma que el mensaje original pueda reconstruirse a pesar de que haya algún error (tampoco deben ser excesivos, porque si no, no es posible). Esos códigos se llaman códigos correctores.

Algunos de esos procedimientos eficientes de corrección de errores se fundamentan en que existan cuadrados latinos ortogonales. Por ejemplo, el código de detección de errores (4, q^2, 3) (para explicar bien que designa esta terna necesitaríamos otro artículo entero; a grandes rasgos quédense con que transmitimos la información en cadenas de 4 dígitos, que contienen q^2 palabras en clave, y el tercero, la distancia, mide el número mínimo de posiciones en las que dos códigos distintos difieren). Pues bien, existe un resultado que dice que un código (4, q^2, 3) existe si, y sólo si, existen un par de cuadrados latinos ortogonales de orden q. Parece complicado, pero créanme, no lo es tanto. Pero describir con cierto detalle un ejemplo, excede el objetivo de estos artículos (no por su complejidad, sino por su desarrollo). Pero el lector interesado puede encontrar esa información sin dificultad.

Dentro de las propias matemáticas (teóricas), por supuesto hay múltiples aplicaciones. Por ejemplo, que exista una familia completa de cuadrados latinos ortogonales de orden n, es equivalente a construir un plano proyectivo finito de orden n. Finalmente, como curiosidad, el original escritor francés Georges Perec concibió su novela 'La vie mode d'emploi' (1978) (en español se editó en 1988 como 'La vida instrucciones de uso') a partir de un cuadrado greco-latino de orden 10.

Alfonso Jesús Población Sáez es profesor de la Universidad de Valladolid y miembro de la Comisión de divulgación de la Real Sociedad Matemática Española (RSME).

El ABCdario de las Matemáticas es una sección que surge de la colaboración con la Comisión de Divulgación de la RSME.