{"id":102578,"date":"2022-02-09T13:16:56","date_gmt":"2022-02-09T18:16:56","guid":{"rendered":"http:\/\/elcuartopoder.com.mx\/nw\/?p=102578"},"modified":"2022-02-09T13:16:58","modified_gmt":"2022-02-09T18:16:58","slug":"ha-resuelto-un-profesor-de-harvard-el-antiguo-problema-de-las-damas-del-ajedrez","status":"publish","type":"post","link":"http:\/\/elcuartopoder.com.mx\/nw\/varios\/ha-resuelto-un-profesor-de-harvard-el-antiguo-problema-de-las-damas-del-ajedrez\/","title":{"rendered":"\u00bfHa resuelto un profesor de Harvard el antiguo problema de las damas del ajedrez?"},"content":{"rendered":"\n

La noticia de la resoluci\u00f3n de un enigma de hace 150 a\u00f1os ha corrido como la p\u00f3lvora, pero las cosas no son tan sencillas<\/h2>\n\n\n\n

Hace unos d\u00edas se difundi\u00f3 en las agencias de noticias y, posteriormente, en algunos medios de comunicaci\u00f3n, la noticia de que un matem\u00e1tico de Harvard hab\u00eda resuelto un problema propuesto hace 150 a\u00f1os. Como todo, hay que hacer algunas matizaciones.<\/p>\n\n\n\n

En 1848, el ajedrecista Max F. W. Bezzel<\/strong> (1824 \u2013 1871) propuso la cuesti\u00f3n de c\u00f3mo disponer ocho damas en un tablero est\u00e1ndar de ocho por ocho escaques de manera que ninguna amenazara al resto (la dama se puede desplazar a todas las de su fila, columna o diagonales). Aunque los matem\u00e1ticos y profesores de matem\u00e1ticas llevemos la fama de proponer problemas y ejercicios de nuestra asignatura constantemente (tanto que gran parte del tiempo de las clases nos la pasamos resolvi\u00e9ndolos y explicando sus soluciones), hay muchas otras disciplinas en las que se plantean montones de ejercicios.<\/p>\n\n\n\n

Los juegos son una parcela importante en estos menesteres, en particular el ajedrez. Y miren ustedes por donde, hay una conexi\u00f3n muy estrecha entre ellos y las matem\u00e1ticas, habida cuenta de que \u00e9stas son capaces de modelizar de modo abstracto pr\u00e1cticamente cualquier actividad humana.<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

Matem\u00e1ticos y ajedrecistas c\u00e9lebres pensaron en el problema de las ocho damas, y encontraron varias soluciones. Entonces se plante\u00f3 la cuesti\u00f3n de cu\u00e1ntas maneras diferentes es posible hacerlo. La primera soluci\u00f3n completa la describi\u00f3 s\u00f3lo dos a\u00f1os despu\u00e9s, en 1850, el matem\u00e1tico Franz Nauck<\/strong>. Y a su vez plante\u00f3 el problema general de las n damas: dado un tablero cualquiera de n x n escaques, \u00bfde cu\u00e1ntas maneras diferentes se pueden disponer n damas, sin que ninguna amenace al resto? Por cierto, una cuesti\u00f3n previa, mucho m\u00e1s sencilla de resolver: \u00bfpodr\u00edan situarse m\u00e1s de n damas verificando esa condici\u00f3n? La respuesta es obviamente negativa, como m\u00e1ximo pueden ser n damas, porque no puede haber m\u00e1s de una por fila y\/o columna. Ahora bien, \u00bfse pueden controlar todas las casillas del tablero con menos de n damas para un tablero n x n? \u00bfCu\u00e1l ser\u00eda el n\u00famero m\u00ednimo, y donde deber\u00edan colocarse? \u00bfY cu\u00e1ntas configuraciones diferentes habr\u00eda?<\/p>\n\n\n\n

Para nuestro problema inicial, en un tablero 8 x 8, hay 92 soluciones<\/strong> (en la imagen anterior vemos una posible), aunque s\u00f3lo 12 de ellas son esencialmente distintas, ya que las restantes se deducen de esa docena por giros y simetr\u00edas. Pero antes de abordar esta situaci\u00f3n, examinemos casos con menos casillas, para comprender mejor el problema.<\/p>\n\n\n\n

Tablero 4 x 4<\/h3>\n\n\n\n

Analicemos el problema en sus primeros casos. Si el tablero fuera de una sola casilla (1 x 1), es evidente que hay una sola manera de colocar una dama. En los tableros 2 x 2 y 3 x 3 no es posible situar respectivamente 2 y 3 damas sin que se amenacen mutuamente. Veamos en el caso 4 x 4.<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

Si colocamos una dama en la primera casilla del tablero 4 x 4 (v\u00e9ase la imagen), teniendo en cuenta las casillas que amenaza (las flechas dibujadas), entonces queda claro que la segunda dama tiene que colocarse en cualquiera de las casillas que no sean esas. Por ejemplo, la podemos colocar en la posici\u00f3n (2, 3) que vemos en el dibujo contiguo. Dibujando de nuevo flechas para ver qu\u00e9 casillas controla, vemos que s\u00f3lo quedar\u00eda la casilla (4, 2) para colocar una tercera dama. Y ya no podr\u00edamos poner ninguna m\u00e1s. Por tanto, no existe soluci\u00f3n cuando colocamos una dama en la primera casilla del tablero.<\/p>\n\n\n\n

Para controlar todas las posibilidades ordenadamente podemos establecer un esquema. Utilizaremos un algoritmo conocido como backtracking <\/strong>(vuelta atr\u00e1s), que suele ser \u00fatil cuando tenemos condiciones o restricciones que cumplir, como es el caso. Fue descrito por primera vez por el matem\u00e1tico norteamericano D. H. Lehmer<\/strong> en la d\u00e9cada de 1950. Funciona del siguiente modo: comenzamos la b\u00fasqueda y en el momento en que llegamos a una contradicci\u00f3n o un valor incorrecto, retrocedemos (de ah\u00ed el nombre de ‘vuelta atr\u00e1s’) a la elecci\u00f3n anterior, y proseguimos desde ah\u00ed. En nuestro caso, sabemos que no podemos tener m\u00e1s de una dama por fila. Enumeramos a las cuatro damas que hay que colocar como Q_1, Q_2, Q_3, Q_4, entendiendo que la primera se va a colocar en la primera fila, la segunda en la segunda, y as\u00ed sucesivamente.<\/p>\n\n\n\n

Comenzamos viendo las posibilidades que hay en la primera fila, en la que colocamos la primera dama (Q_1) en la primera casilla de la primera fila (posici\u00f3n (1, 1)). Como esa dama controla las casillas de la primera fila y la primera columna, como vemos en la imagen anterior, en ellas no podemos colocar la dama Q_2 que debe ir en la segunda fila. S\u00f3lo podemos colocarla en las columnas 2, 3 o 4. Por eso en el gr\u00e1fico en \u00e1rbol que vemos a continuaci\u00f3n, salen flechas s\u00f3lo para la segunda fila a las columnas 2, 3 y 4. Ahora bien, como la dama tambi\u00e9n controla la diagonal, la segunda dama no se puede poner tampoco en la casilla (2, 2). Por eso, bajo el n\u00famero 2 se ha colocado una cruz de color rojo, porque esa posibilidad no se puede dar. Volvemos entonces atr\u00e1s, a la columna 3 de la segunda fila, y all\u00ed colocamos la segunda dama, Q_2. Como antes, esa dama controla su fila y su columna, por lo que bajo el 3 no puede haber otro 3. Nos quedan entonces como posibilidades solamente las columnas 2 y 4 (recordemos que la 1 quedaba descartada por haber colocado all\u00ed la primera dama, Q_1). \u00bfPodr\u00edamos colocar la tercera dama Q_3 en las columnas 2 o 4? Viendo las casillas en diagonal que controla Q_2, vemos que ninguno de los dos casos es posible. Por eso, bajo el 2 y el 4 de la tercera fila aparecen las consiguientes cruces rojas, porque por ah\u00ed no se puede continuar. Volvemos entonces atr\u00e1s, y consideramos la posibilidad de colocar Q_2 en la columna 4 en lugar de en la 3. Y vamos razonando del mismo modo en cada caso. Comprobamos as\u00ed que no es posible colocar las cuatro damas en el tablero 4 x 4 cuando ponemos la primera en la posici\u00f3n (1, 1).<\/p>\n\n\n\n

La siguiente posibilidad ser\u00eda colocar la primera dama Q_1 en la posici\u00f3n (1, 2), es decir, primera fila, segunda columna. Como antes, bajo el 2 del esquema s\u00f3lo podremos situar la segunda dama en las columnas 1, 3 y 4 (a las que vemos que van las flechas). Sin embargo, ni en la columna 1 ni en la 3 de la segunda fila podr\u00edamos colocar la segunda dama, porque esas diagonales las controla Q_1. Por eso, bajo los n\u00fameros 1 y 3 aparecen sendas cruces rojas. No quedar\u00eda m\u00e1s remedio que colocarla entonces en la columna 4. Y as\u00ed vamos razonando con cada caso. El esquema muestra todas las posibilidades, habi\u00e9ndose marcado en color verde, las \u00fanicas dos posibilidades de soluci\u00f3n del problema.<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n

Esas dos soluciones podemos describirlas en una sola l\u00ednea como 2413 y 3142. Ser\u00edan las que aparecen en los siguientes cuadros, respectivamente. Tras confirmar que, en efecto, son las posiciones de 4 damas en un tablero 4 x 4 sin que ninguna amenace a las dem\u00e1s, observamos que tienen algo en com\u00fan: son sim\u00e9tricas respecto a un imaginario eje vertical central (tambi\u00e9n respecto a uno horizontal). Por eso, para los matem\u00e1ticos, en realidad es una \u00fanica soluci\u00f3n, porque una se puede deducir de la otra por simetr\u00eda. En este tipo de ejercicios suele decirse ‘tantas soluciones’, a\u00f1adiendo la coletilla ‘salvo giros o simetr\u00edas’. Obs\u00e9rvese que la simetr\u00eda puede detectarse tambi\u00e9n en la forma descrita num\u00e9ricamente: 3142 es 2413 escrito del final al principio.<\/p>\n\n\n\n

Si tienen \u00e1nimo pueden tratar de deducir con razonamientos an\u00e1logos al de 4 x 4, c\u00f3mo ser\u00edan las soluciones de los casos 5 x 5, 6 x 6, etc. En el siguiente cuadro se recogen las posibilidades que existen hasta orden 10:<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

Tablero 8 x 8<\/h3>\n\n\n\n

Como indicamos anteriormente, el problema original de las 8 damas fue resuelto a los dos a\u00f1os de su planteamiento. En el libro ‘Ajedrez y Matem\u00e1ticas<\/strong>‘ (Ed. Mart\u00ednez Roca, 1974) aparecen descritas las 12 soluciones diferentes al mismo. Con la notaci\u00f3n expuesta anteriormente ser\u00edan<\/p>\n\n\n\n

1) 15863724<\/p>\n\n\n\n

2) 16837425<\/p>\n\n\n\n

3) 24683175<\/p>\n\n\n\n

4) 25713864<\/p>\n\n\n\n

5) 25741863<\/p>\n\n\n\n

6) 26174835<\/p>\n\n\n\n

7) 26831475<\/p>\n\n\n\n

8) 27368514<\/p>\n\n\n\n

9) 27581463<\/p>\n\n\n\n

10) 35281746<\/p>\n\n\n\n

11) 35841726<\/p>\n\n\n\n

12) 36258174<\/p>\n\n\n\n

Todas ellas tienen 7 simetr\u00edas diferentes (aparte de la descrita), salvo la d\u00e9cima que s\u00f3lo tiene 4 (la dada y las de giros de 90\u00ba, 180\u00ba y 270\u00ba del tablero). Una sencilla cuenta nos da por tanto todas las soluciones posibles: 11 x 8 + 4 = 92. Un n\u00famero peque\u00f1o si tenemos en cuenta que ocho damas pueden colocarse en 61 escaques, \u00bfde cu\u00e1ntas formas? (Repasen la Combinatoria<\/strong>: ser\u00edan combinaciones de 64 elementos tomados de 8 en 8, es decir, 4.426.165.368 solamente).<\/p>\n\n\n\n

En la primera imagen de este art\u00edculo aparece la soluci\u00f3n 47382516. Es una situaci\u00f3n sim\u00e9trica de las 12 dadas anteriormente. \u00bfSaben de cu\u00e1l de ellas?<\/p>\n\n\n\n

Tablero n x n<\/h3>\n\n\n\n

Conforme aumenta el n\u00famero de filas y columnas del tablero, el n\u00famero de soluciones crece considerablemente. En el caso de un tablero 20 x 20, por ejemplo, el n\u00famero de soluciones diferentes es de 4.878.666.808 y el total, contando todas sus simetr\u00edas y giros de 39.029.188.884. Todas ellas se han calculado con algoritmos y ordenadores. Pero no existe una expresi\u00f3n general que nos diga \u00e9sta o aquella es esa cantidad.<\/p>\n\n\n\n

El becario postdoctoral Michael Simkin<\/strong>, del Centro de Ciencias y Aplicaciones Matem\u00e1ticas de la Universidad de Harvard (Cambridge, Massachusetts, EE. UU.) y Zur Luria<\/strong>, graduado de la Universidad hebrea de Jerusal\u00e9n y experto ajedrecista, han estado cinco a\u00f1os trabajando en el problema, con varios art\u00edculos publicados. Hace unas semanas Simkin ha publicado un nuevo art\u00edculo en solitario en el que recapitula todas sus investigaciones y explica con cierto detalle los algoritmos desarrollados en sus trabajos. Los medios de comunicaci\u00f3n se han hecho eco de la noticia recalcando, como siempre, lo espectacular: que si es un problema planteado hace 150 a\u00f1os, que si ha logrado dar una cota inferior al valor exacto, es decir, una aproximaci\u00f3n al n\u00famero m\u00ednimo de configuraciones posibles, y es la cifra m\u00e1s cercana que se puede obtener en este momento todas estas configuraciones distintas para un tablero n x n:<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

Y m\u00e1s. Si el lector calcula los valores que esa expresi\u00f3n desde n igual a 1 en adelante, y los compara con los valores exactos que hemos descrito en la tabla descrita m\u00e1s arriba, realmente no parecen aproximaciones demasiado ‘buenas’: [0.143, 0.0817, 0.0789, 0.10704, 0.1868, 0.3989, 1.007, 2.9336, 9.68739, 35.7569] y probablemente exclame: \u00ab\u00a1\u00a1Cinco a\u00f1os para esto!!\u00bb.<\/p>\n\n\n\n

Cuando un matem\u00e1tico lee ese tipo de noticias, con valores num\u00e9ricos como ese 0.143, lo primero que hace es preguntarse \u00ab\u00bfde d\u00f3nde sale?\u00bb. Y acaba yendo a la fuente original, al art\u00edculo. Y descubre que las cosas no son tan simples como han difundido los medios de comunicaci\u00f3n. Para empezar, con un vistazo r\u00e1pido, el art\u00edculo<\/a> (de 51 p\u00e1ginas) contiene un mont\u00f3n de resultados, proposiciones y demostraciones nada triviales, y adem\u00e1s ese 0.143 no aparece por ninguna parte. Bueno, aparece, pero no as\u00ed.<\/p>\n\n\n\n

El objeto del art\u00edculo es demostrar que, si Q(n) son el total de posibles configuraciones en que una dama puede colocarse en un damero n x n sin que ninguna est\u00e9 amenazando a ninguna de las dem\u00e1s, entonces existe una constante \u03b1 que se encuentra en el intervalo (1.94, 1.9449) tal que:<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

Es decir que, asint\u00f3ticamente (a grandes rasgos, que los valores son m\u00e1s precisos cuanto m\u00e1s grande es n; por eso los valores de n peque\u00f1os resultan muy malos), el n\u00famero de configuraciones se ‘acerca’ a esa cota inferior. Por cierto:<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

de ah\u00ed el 0.143 de la f\u00f3rmula. Del l\u00edmite anterior, para n lo suficientemente grande (detalle que se obvia y es muy importante para entender lo que se ha obtenido):<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

lo cual ‘acerca’ el resultado del paper con lo publicado en los medios de comunicaci\u00f3n.<\/p>\n\n\n\n

En dicho art\u00edculo Simkin ha utilizado algoritmos de tipo probabil\u00edstico y combinatorio: esencialmente algoritmos voraces aleatorios y de absorci\u00f3n. Su mecanismo no es dif\u00edcil de comprender; en posteriores entregas podemos explicar brevemente en qu\u00e9 consisten a grandes rasgos, con ejemplos entendibles. Mediante otros algoritmos (concretamente uno de tipo entrop\u00eda), el autor ha determinado tambi\u00e9n un l\u00edmite superior al n\u00famero de posibles configuraciones, es decir, el mayor n\u00famero posible de ellas, de modo que tenemos acotado el valor exacto entre dos aproximaciones, que no distan mucho entre s\u00ed, para cualquier valor de n, por grande que sea. Pero de nuevo, con el matiz que hemos comentado para interpretar esas cotas.<\/p>\n\n\n\n

Por Alfonso J. Poblaci\u00f3n<\/p>\n","protected":false},"excerpt":{"rendered":"

La noticia de la resoluci\u00f3n de un enigma de hace 150 a\u00f1os ha corrido como la p\u00f3lvora, pero las cosas no son tan sencillas Hace unos d\u00edas se difundi\u00f3 en las agencias de noticias y, posteriormente, en algunos medios de comunicaci\u00f3n, la noticia de que un matem\u00e1tico de Harvard hab\u00eda resuelto un problema propuesto hace […]<\/p>\n","protected":false},"author":2,"featured_media":102579,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[64],"tags":[],"class_list":["post-102578","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-varios"],"_links":{"self":[{"href":"http:\/\/elcuartopoder.com.mx\/nw\/wp-json\/wp\/v2\/posts\/102578","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/elcuartopoder.com.mx\/nw\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/elcuartopoder.com.mx\/nw\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/elcuartopoder.com.mx\/nw\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/elcuartopoder.com.mx\/nw\/wp-json\/wp\/v2\/comments?post=102578"}],"version-history":[{"count":1,"href":"http:\/\/elcuartopoder.com.mx\/nw\/wp-json\/wp\/v2\/posts\/102578\/revisions"}],"predecessor-version":[{"id":102580,"href":"http:\/\/elcuartopoder.com.mx\/nw\/wp-json\/wp\/v2\/posts\/102578\/revisions\/102580"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/elcuartopoder.com.mx\/nw\/wp-json\/wp\/v2\/media\/102579"}],"wp:attachment":[{"href":"http:\/\/elcuartopoder.com.mx\/nw\/wp-json\/wp\/v2\/media?parent=102578"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/elcuartopoder.com.mx\/nw\/wp-json\/wp\/v2\/categories?post=102578"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/elcuartopoder.com.mx\/nw\/wp-json\/wp\/v2\/tags?post=102578"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}