Cuadrados grecolatinos y la conjetura de Euler

Os propongo un divertido entretenimiento: cojamos todos los ases, reyes, reinas y jotas de una baraja de cartas, y dispongámoslos en un cuadrado 4×4 de modo que en cada fila y cada columna aparezcan los cuatro palos y las cuatro figuras. Este problema no es difícil y se pueden encontrar varias soluciones. De hecho hay 1152 soluciones diferentes, que en realidad son variantes (reflexiones y rotaciones) de las dos clases siguientes:

La solución de este problema se denomina cuadrado greco-latino o cuadrado de Euler. La atribución a Euler  es debida a que en 1782 planteó un problema similar de orden 6. Se trata de “El problema de los treinta y seis oficiales“. La pregunta es si es posible colocar a treinta y seis oficiales de seis regimientos diferentes y de cada uno de los seis grados (en cada regimiento) en un cuadrado de 6×6 de forma que no coincidan dos oficiales del mismo rango o del mismo regimento en ninguna fila y en ninguna columna. La respuesta es no. No es posible constuir cuadrados de orden 6.

Las preguntas que surgen entonces son: ¿para qué órdenes existen cuadrados grecolatinos?, ¿para cuáles no?, ¿pueden encontrarse cuadrados grecolatinos de un orden cualquiera? El gran Euler (cómo no) demostró que el problema podía resolverse siempre que el lado del cuadrado fuese impar o multiplo de cuatro (par de clase par) y conjeturó que no existía ninguna solucción posible cuando era par de clase impar (multiplo de 2 que no es multiplo de 4), por ejemplo 6, 10, 14, etc.

El gran Leonhard Euler

Tuvieron que pasar muchos años para que Gaston Tarry, en 1901, demostrase la conjetura de Euler para orden 6. Sin embargo el problema seguía abierto para orden 10 o superiores. En 1959, R.C. Bose y S. S. Shrikhande construyeron algunos contraejemplos de orden 22 siguiendo puntos de vista matemáticos, lo cual contradecía la hipótesis de Euler. Poco más tarde E. T. Parker encontró un contraejemplo del orden 10 utilizando en la búsqueda una computadora UNIVAC (lo que hace que sea uno de los primeros problemas de combinatoria resueltos con ordenador). Finalmente, en 1960, Parker, Bose, y Shrikhande demostraron que la conjetura de Euler es falsa no sólo para n=10, sino para todo n ≥ 10, múltiplo de 2, pero no de 4. Euler se equivocaba.

Este juego matemático parecería que no tendría ninguna utilidad en la vida cotidiana, pero nada más lejos de la realidad. Los cuadrados grecolatinos se utilizan en el diseño de experimentos o en la programación de torneos. Por ejemplo, si tenemos los equipos de tenis de Argentina y España, compuesto por cuatro componentes cada uno, y queremos diseñar un torneo donde todos jueguen con todos, en cuatro días diferentes y, por supuesto, en cuatro escenarios diferentes, pues recurriremos a un cuadrado grecolatino de orden 4.

Cuadrado grecolatino de orden 4

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s