4: Diez prisioneros y una bombilla

Si existe un problema cuyo enunciado me haya dejado turulato, es este: el problema de los diez prisioneros y la bombilla.
Antes de exponerlo, me gustaría puntualizar un matiz, que para los ajedrecistas es muy conocido: los problemas se pueden enfrentar con mentalidad táctica o con mentalidad estratégica.

Si piensas "Poniendo aquí el caballo, el rival lo eliminará con su álfil; y a continuación, yo podré eliminar su álfil y un peón, con lo que saldré ganando" tienes mentalidad táctica; buscas maniobras que te den un resultado tangible y a corto plazo.

Si piensas "Creo que la primera columna que se va a quedar libre de peones es la columna del álfil de dama (columna c); para cuando llegue ese momento, voy a ir colocando una mis torres en esa columna" tienes mentalidad estratégica; buscas ventajas invisibles y a largo plazo.

Aprovecho la ocasión para añadir que las jugadas de un buen estratega son incomprensibles para el jugador ocasional (que suele ser táctico al 95%), de modo que aparcar la mentalidad táctica y desarrollar la capacidad estratégica es lo que hace que crezca el número de personas que después de la partida le dicen a sus amigos en voz baja "Me ha ganado y es que no sé ni cómo".

¿Y cómo se desarrolla la visión estratégica? Obvio: resolviendo situaciones que carezcan de componente táctica: no hay piezas que comer, no hay casillas que ocupar, no hay elementos tangibles que mover de un sitio a otro... jugando a juegos que sean estrategia pura.

O resolviendo problemas estratégicos. Como el problema de los diez prisioneros y la bombilla. Estrategia en estado puro.
El enunciado dice así:

Diez prisioneros, han sido llevados a una sala con aspecto de aula de escuela, 
donde se les ha dicho que tomen asiento.  
El director de la prisión se coloca frente a ellos y les dice:
"Todos vosotros tenéis por delante una condena de cinco años.
Pero puede que os marchéis de la prisión mucho antes.
Cuando salgáis de esta sala, 
se os llevará a celdas separadas e incomunicadas. 
Empezando mañana, cada día, antes del desayuno, 
se elegirá a uno de vosotros al azar, y se le llevará a una habitación 
en la que no hay más que una bombilla y un interruptor. 
La bombilla no admite más opciones: o apagada o encendida. 
El prisionero que vaya mañana se la encontrará apagada 
y deberá decidir si la deja apagada o la enciende. 
Cada prisionero, cuando vaya a la habitación de la bombilla, 
puede dejarla como se la encuentre o puede pulsar el interruptor 
y cambiarla de estado, no pudiendo tocar absolutamente nada 
excepto el interruptor.
Si algún día, un prisionero cualquiera, al llegar a la habitación de la bombilla,
afirma "Ya hemos pasado los diez por la habitación" y es verdad, 
los diez serán puestos en libertad de forma inmediata.
Si algún día, un prisionero cualquiera, al llegar a la habitación de la bombilla,
afirma "Ya hemos pasado los diez por la habitación" y no es verdad, 
los diez serán ejecutados de forma inmediata.
Disponéis de una hora para deliberar y acordar una estrategia.
Pasado ese tiempo, se os llevará a la celda incomunicada".

Creo que es mi enunciado favorito. ¿A quién se le ha podido ocurrir? Lo pregunto a sabiendas de que no hay constancia de quién es el autor.

Y bien... ¿qué estrategia propones?
Si fueses uno de los diez... ¿qué dirías?
¿Puede ser lo mejor no arriesgarse y dejar pasar los cinco años de condena?
¿Dejamos que decida el azar, sorteamos un prisionero, y cuando lo lleven por tercera vez a la sala de la bombilla que diga "Ya hemos pasado todos por esta habitación"? Si alguien va por tercera vez, parece lo más probable que todos los demás ya hayan ido al menos una vez... ¿o mejor que lo diga a la cuarta?
¿O nos limitamos a dejar pasar un año y en cuanto pase "nos la jugamos"?
Hay demasiado en juego: si metemos la pata nos ejecutan ese mismo día.
¿Qué es lo mejor?

Vamos a pensarlo.
Dentro de unos días, colgaré una solución que me parece muy buena.
(Al final, han sido meses y no días lo que he dejado pasar... ¡Quién iba a contar con un accidente en el autobús, precisamente cuando se pone a escribir sobre PROBABILIDADES!)


SOLUCIÓN

Empezaremos con el “Enfoque erróneo número uno”. Dice así:

“Todos sabemos que al lanzar un dado común, la probabilidad de que salga un número cualquiera es un sexto. Por tanto, el número de lanzamientos teóricos necesarios para que salga un número cualquiera será seis. Si queremos que salgan los seis números, ¿cuántas tiradas deberemos esperar?

Fácil de calcular. En la primera tirada nos sirve cualquier número; en la segunda, cinco de seis; en la tercera, cuatro de seis... Como el tiempo que debemos esperar para que algo ocurra (o el número de tiradas que debemos hacer) es inversamente proporcional a su probabilidad, el número de tiradas necesarias para que salgan los seis números es:

Por tanto, cabe esperar que todos y cada uno de los seis números del dado hayan salido al cabo de 15 tiradas.

Aplicando el mismo razonamiento a los prisioneros, nos quedaría:

De donde concluiríamos que los diez habrán pasado por la habitación de la bombilla al cabo de 29’3 días. Añadimos una semana de margen de seguridad... El que entre el día 36º que diga “Ya hemos pasado todos por aquí” y listo; todos libres.”

¡¡ERROR!!

En el caso de los dados, 14’7 es “El valor frontera” que determina a partir de qué momento las probabilidades están a mi favor.

Si apuesto a “Con 13 tiradas voy a lograr los seis números”, a largo plazo acabaré perdiendo.

Si apuesto a “Con 10 tiradas voy a lograr los seis números”, a largo plazo acabaré perdiendo hasta las pestañas.

Si apuesto a “Con 16 tiradas voy a lograr los seis números”, a largo plazo acabaré ganando.

Si apuesto a “Con 20 tiradas voy a lograr los seis números”,  y encuentro incautos que acepten, a largo plazo acabaré ganando y mucho. Es más, como 20 es 15 incrementado un 33’3%, podemos redondear a lo bruto que voy a ganar al menos el 80% de los juegos, así que podría ofrecer 3:1 y a largo plazo seguiría ganando yo.

Inciso: hay gente que se mete en bwin sin saber qué es el valor frontera; los que están detrás de la maquinita sí que lo saben; luego pasa lo que pasa: a la larga, siempre ganan los dueños de la maquinita. Eso no quiere decir que los espíritus matemáticos no entremos en bwin; lo que quiere decir es que no apostamos ni un céntimo a probabilidades ridículas por mucho que se paguen mil a uno. De hecho, los dueños de bwin saben perfectamente que una pequeña parte de sus clientes cierran cada mes con ganancias (son los que hacen apuestas de sistema 3/7 o 4/7 sobre sucesos que se paguen 1’4:1 o 1’3:1). Y a los dueños de bwin les da igual. ¿Por qué? Pues porque también saben que son mayoría los que apuestan a lo loco. Y el que apuesta a lo loco puede acertar algún día una apuesta rara del tipo "Roger Federer cae derrotado en dos sets contra un esquimal desconocido", pero a la larga siempre va a perder; y el negocio, para los dueños, que razonan a muy largo plazo, seguirá siendo redondo.

Pues eso es precisamente la cifra 29’3. El valor frontera de nuestro problema de los prisioneros. Arriesgarte antes del día 29º sería una temeridad; antes del 20º, directamente se llama intento de suicidio. A partir del día 30 las probabilidades empiezan a estar a tu favor... ¡¡¡pero te estás jugando la vida!!! ¿A alguien le apetece poner su vida en manos de la buena suerte? Habrá que calcular algo más valioso que el valor frontera.

Veamos el “Enfoque erróneo número dos”.

“Si sabemos calcular el valor a partir del cual las probabilidades pasan a ser más del 50% a mi favor, también podré calcular a partir de qué día las probabilidades a mi favor alcanzan el 99%”; y ese día..., adiós a la cárcel.”

Claro que se puede calcular. Hagámoslo.

En principio, en lugar de un problema con 10 prisioneros y d días, ataquemos algo más simple: hagamos las cuentas del caso 3 prisioneros (A, B, C) y 3 días.
Casos FAVORABLES (Entran los tres): tres letras DIFERENTES ordenadas en tres posiciones:

O sea: Permutaciones de 3 sin repetición: 3!=3.2.1=6.

En efecto, ABC, ACB, BAC, BCA, CAB, CBA: 6.  

Casos DESFAVORABLES (Algún prisionero se queda sin entrar):

Habrá quien piense que viene dado por “Combinaciones con repetición de 3 sobre 3”:

Hagamos el recuento, a ver si tienen razón:

AAB, BBA, CCA, AAC, BBC, CCB, ABA, CBC, BCB, ACA, CAC, BAB, ABB, ACC, BAA, BCC, CBB, CAA: 18

y además AAA, BBB, CCC: 3.

Total: 21.

Pues no; no tienen razón. (Por supuesto, los casos totales son tres al cubo, 27; 6+21=27) 
Las fórmulas de combinatoria que se estudian (supuestamente) en secundaria sólo son de fiar cuando se trata de elegir subconjuntos de elementos con menor cardinal que el conjunto de partida; o sea, con menos elementos.

En nuestro caso, con 3 prisioneros y cinco días, un subconjunto posible sería: AACBA. Cinco elementos. Y el conjunto de partida sólo tiene 3: {A,B,C}. Más vale que en las fórmulas de combinatoria clásica tengamos una fe moderada: aquí no valen.

Hay que proceder de otro modo: para obtener ese “21” hay que calcular los casos en que han entrado dos prisioneros distintos o menos [ (combinaciones de 2 sobre 3)  multiplicadas por las formas en que pueden ordenarse sus visitas a la celda durante tres días (variaciones con repetición de 3 sobre 2) y restarle los casos en que han entrado un prisionero  distinto o menos (los casos AAA, BBB, CCC) porque si no los estaríamos contando dos veces ]. O sea:

¿Lo podemos generalizar para p prisioneros y d días?

Claro que sí; ¿por qué no se va a poder?

Generalizando Casos posible y Casos favorables, obtenemos esta preciosidad de fórmula, que no creo que nadie haya visto escrita en ningún sitio antes de hoy:

Y por supuesto, se cumple P(hayan entrado todos)=Cf dividido por Cp.

Ahora podemos fijar P(hayan entrado todos)=0’99, p=10 y calculamos d (por tanteo, obviamente... esa d no la despeja ni Batman). Resultado: d=66.

Así que con esperar dos meses y una semana, listo... Las probabilidades de éxito serían del 99%. Al legar el día 66, decimos que ya hemos pasado todos y listo; a casa. 

¡¡ERROR!!

Sigue habiendo un 1% en tu contra y lo que te estás apostando es la vida.

Una bolsa con 99 bolas blancas y una bola negra... Sólo hay una, sí, sólo una, es enormemente improbable... pero si metes la mano y sacas la bola negra te dejan fumarte tu último pitillo y te matan. ¿Te arriesgarías? 

Dado que nos jugamos la vida, lo correcto es buscar una estrategia que nos permita tener la certeza total de acierto.

¿Se puede?

Claro que sí... vamos a pensar un poco.

Supongamos que sólo puedo hablar yo. Para decir “Ya hemos pasado todos por esta habitación”, lo que necesito es que mis compañeros me dejen el mensaje de que ya han estado: o sea, que enciendan la bombilla; cuando la vea encendida, yo – que soy el único que tiene derecho a apagarla – la apago. Cuando la apague por novena vez puedo decir con certeza absoluta que todos hemos pasado por la habitación de la bombilla. Por supuesto, cada uno de mis compañeros debe encender la bombilla sólo la primera que le ocurra el suceso “entro en la habitación y me encuentro la bombilla apagada”. El resto del tiempo ya no tiene que hacer nada.

No sabemos si  saldremos de la cárcel el día 58º, el 79º, el 84º o el 136º o el que sea... De hecho las probabilidades no empiezan a ponerse a nuestro favor hasta bien avanzado el cuarto mes; o sea que lo más probable es que pasemos enchironados cinco meses y pico; pero sabemos que vamos a salir vivos, que no es poco.

Y este método, ¿se puede mejorar?

Claro.  

Hemos partido de la base de que soy yo el único que puede hablar. Pero... ¿y si pasa el primer mes completo – el azar es MUY caprichoso – y siguen sin llamarme a mí? Menudo desperdicio de tiempo. De entre los diez prisioneros, hay que elegir como “portavoz” a aquel cuya fecha de entrada en la habitación nos permita ahorrar más tiempo.

¿Y eso cómo se hace?

Aplicando dos subrutinas distintas.

> Subrutina de los primeros diez días: “Un prisionero cualquiera A sólo encenderá la bombilla si es la segunda vez que entra en la habitación y se la encuentra apagada. Dicho prisionero quedará nombrado “portavoz”. El único que tiene derecho a apagarla es el prisionero B que entre a la habitación el día 10º; y en ese momento, dejando la bombilla apagada, empezará la subrutina del resto de los días.

¿Hay que modificar algo si A=B? Nada.

¿Qué hace el prisionero B si al entrar en la habitación el día 10º con intención de apagar la bombilla, llega allí y se la encuentra apagada? Pues darle las gracias a todos los santos del cielo por haber tenido tantísima suerte (es prácticamente imposible), decir en voz bien alta “Ya hemos pasado todos por esta habitación”. Y luego ponerse a gritar “Nos vamos a casita, chicos”. Doy por hecho que todo el mundo ve como una obviedad que si el 10º se encuentra la bombilla apagada quiere decir que ya han pasado los otros nueve.

> Subrutina del resto de los días. La misma que hemos visto cuando “el portavoz era yo”.

¿Hemos ganado algo? Claro que sí. Si el que enciende la bombilla lo hace al entrar por segunda vez el día 8º, sabe que ya han pasado por la habitación SEIS de sus compañeros. Durante la segunda fase ya no tendrá que contar hasta NUEVE. Sólo tendrá que contar hasta TRES.

De esta manera – calcular el valor  exacto es muy complicado y yo ya me hago viejo, pero debe estar alrededor de 85 días – lo más probable es que no lleguemos a completar un trimestre en la cárcel. Comparado con cinco años...

3: El problema del quitanieves

La primera versión del problema del quitanieves 

la inventó Ralph Palmer Agnew (1900-1986), 

matemático de la Cornell University, New York.

Si a alguien le gusta esta entrada, 

que me aplauda un poquito a mí y mucho a él.

Empezamos.

Existen problemas físico-matemáticos muy fáciles de resolver, por ejemplo este: "Calcular cuántas calorías desprende una resistencia de 100 Ω, si circula por ella 1 A durante cinco minutos". 

Es muy fácil porque basta con saberse la fórmula correspondiente Q=I².R.t, y tener cuidado con las unidades. Como el tiempo debe expresarse en segundos, tenemos 

                 Q=1.100.300=30.000 Julios=3.10⁴ J.

 y como la solución nos la piden en calorías, nos queda 

                   Q=0’24.3.10⁴=7’2.10³ cal.

Otros problemas, en cambio, no son nada fáciles. No lo son porque no hay fórmula a la que podamos acudir, para sustituir los datos en ella. En lugar de eso, si queremos resolverlos, debemos pararnos a pensar. De ahí que se aprenda diez veces más resolviendo uno de estos que resolviendo mil como el anterior. Uno de mis ejemplos favoritos de "Problemas que obligan a pensar" es el problema de la máquina quitanieves. Dice así:

     "Nevaba de forma constante y uniforme. 
     Para retirar la nieve acumulada en una carretera recta y horizontal, 
     un quitanieves con una pala de anchura a metros, 
     empezó a trabajar a las 12.00 horas. 
     En la primera hora, limpió dos kilómetros. 
     En la segunda hora, limpió uno. 
     ¿A qué hora había empezado a nevar?"

Lo primero que uno debe hacer es reponerse de la sorpresa. Y luego pensar. Que no mata.


SOLUCIÓN


PRIMERO

Empecemos por hacer  una suposición razonable: el volumen de nieve retirado por unidad de tiempo es constante, de modo que cuanto mayor es el espesor de nieve acumulado, más lento avanza la máquina (nos lo confirma el enunciado). Así que nuestra ecuación de partida será

donde

a: anchura de la pala quitanieves (constante)

x: espesor de nieve acumulada (variable creciente)

v: velocidad de avance de la máquina (variable decreciente)

k: ritmo de retirada de la nieve.

Con las unidades que nos propone el enunciado [km, h] comprobamos que la ecuación sea homogénea, esto es, que tenga las mismas unidades a izq y dcha:

SEGUNDO

La letra v sólo tiene derecho a estar presente en una fórmula cuando es constante; como en nuestro problema la velocidad es variable, deberemos escribir en lugar de la letra v su concepto, o sea, la derivada del espacio recorrido respecto al tiempo transcurrido. Si al espacio recorrido por la máquina quitanieves lo designamos con la letra y nuestra ecuación queda así:

Como la x también es variable, deberemos escribir en su lugar la función que nos establezca su dependencia respecto al tiempo. Llamando s al ritmo al que está nevando [constante porque lo dice el enunciado], o sea, a los km/h que aumenta el espesor de la nieve, tenemos que x=s.t

                        

Y nuestra ecuación de partida nos queda

                               

TERCERO

Hay que decidir dónde ponemos el contador de tiempo a cero. Ralph Palmer Agnew resolvió la primera versión de este problema poniendo el origen de tiempos a las 12.00, de modo que el problema nos pide la concreción de un instante que está en el pasado (tiempo negativo).  Es más intuitivo poner el origen de tiempos en el instante en que empieza a nevar. Desde ese instante hasta las 12.00 habrá pasado un tiempo T, hasta las 13.00 un tiempo T+1 y hasta las 14.00 un tiempo T+2, siendo T lo que se nos pide averiguar. De este modo, todos los tiempos son positivos.

CUARTO

La ecuación (3) es una ecuación diferencial (obvio: contiene una derivada). Deberemos empezar por obtener a partir de ella la correspondiente ecuación lineal. Habrá que integrar.

Despejando la derivada:
             

Integrando:  

Para averiguar el valor de la constante de integración, sabemos que cuando t=T, y=0, de donde:

                         

Así que nuestra ecuación inicial se transforma en 

         
QUINTO

Ahora sí que podemos sustituir los dos datos disponibles: cuando t=T+1, y=2; cuando t=T+2, y=3. Llegamos a este sistema de ecuaciones, realmente precioso:

Despejando la parte constante e igualando, nos queda:

                     

Ahora hay que recordar las propiedades de los logaritmos:

        

El resto tiene poco misterio

Como la solución negativa no tiene sentido físico, nos queda T=0’608 horas.
O sea, T=0 horas 37 min 5 s.

Conclusión: Había empezado a nevar a las 11h 22 min 55 s.

OBSERVACIÓN FINAL

I.- Todo alumno de segundo de bachillerato debería ser capaz de rehacer este desarrollo en un folio en blanco. Si cursa Matemáticas, claro. Y si no las cursa, él se lo pierde. O ella.

II.- En la próxima entrada veremos otro tipo de problema matemático: tiene un montón de soluciones pero es dificilísimo estar seguro de que alguna de ellas - alguna de las que ya ha encontrado alguien - sea la mejor de todas las posibles, la solución óptima. ¿Y si hemos encontrado treinta soluciones pero la óptima todavía está esperando un descubridor que piense en ella?
Para ilustrar ese tipo de problemas veremos uno fascinante: "El problema de los prisioneros y la bombilla".

2: Sam Loyd y el Taken

Hace 20 ó 30 años, casi todo mi tiempo libre era devorado por Caissa, la diosa ingrata de los ajedrecistas.
En el templo de los 64 escaques conocí a Samuel Loyd, compositor de problemas endiablados. Sirva este como ejemplo, en el que las blancas deben dar mate en tres movimientos, cosa a primera vista imposible. La solución, por si alguien se rinde, puede verse al final de esta entrada.

Samuel Loyd, también compuso otros puzzles de inspiración matemática, como este, llamado Klondike, que es uno de sus inventos más famosos

cuyas instrucciones dicen así:

Comenzar a partir del corazón que se encuentra en el centro e ir tres pasos en línea recta, en alguna de las ocho direcciones, norte, sur, este u oeste, o en el sesgo, como dicen las señoras, noreste, noroeste, sureste o suroeste. Cuando haya avanzado los tres pasos en línea recta, usted estará parado sobre una baldosa con un número inscrito en ella, que indica la cantidad de pasos a recorrer en su segundo día: avance la cantidad de pasos indicada en una línea recta en cualquiera de las ocho direcciones. Desde este nuevo punto, cuando llegue, debe caminar de nuevo de acuerdo con el número indicado en la nueva baldosa, y continuar después, según indiquen las baldosas a las que vaya usted llegando, hasta que llegue a una baldosa con un número que le permita caminar JUSTO un paso más allá de la frontera. Al llegar a este punto usted habrá salido de los bosques y puede caminar todo lo que quiera ya que habrá resuelto el rompecabezas.

Hasta aquí nada que objetar. Hallar la solución del Klondike, por ejemplo, sólo requiere paciencia franciscana.
Pero, acabando la década de 1870, Samuel Loyd inventa algo esencialmente distinto: el "Juego del 15", o "Juego del Jefe", o "Jeu de Taquin" o a raíz de la pronunciación francesa "Juego del Taken". Este juego no aparece en escena como otros, ocupando en los escaparates el lugar destinado a las novedades. No, nada de eso.
Las cajitas de madera con este aspecto,

cuyas fichas numeradas pueden deslizarse por filas y columnas gracias al hueco que deja la inexistente ficha "16", se ponen a la venta en esta posición,

junto con el anuncio de un premio de mil dólares para quien descubra la secuencia de movimientos que lleva a esta otra posición

Mil dólares de 1880 vienen a ser, haciendo la cuenta a lo bestia y redondeando sin miramientos, dos millones de euros de 2012.

Se desató la locura. No sólo en EEUU. En medio mundo. Los casos más graves se pasaban día y noche dándole vueltas al problema. Había quien se encerraba donde fuese durante el tiempo de trabajo para seguir probando variantes sin que su jefe lo viese (de ahí uno de los nombres del juego). Hubo quien rozó el abismo de la demencia. Hubo quien cayó en él. Hubo quien iba bien en los estudios y dejó de estudiar, absorbido por el Jeu de Taquin. Hubo matrimonios rotos.

En 1882, varias empresas estadounidenses se ponen de acuerdo: "Quien sea sorprendido durante la jornada laboral manipulando la dichosa cajita de las quince fichas, será despedido en el acto". Hay cientos de despidos. En Inglaterra y en Holanda también se dan casos muy graves aunque en territorio europeo la peor parte le toca a Alemania y a Francia. En Alemania se llegan a detener sesiones parlamentarias porque nadie hacía caso al ponente. En Le Monde, un prestigioso columnista opina que el jeu de Taquin es un azote para la humanidad, una maldición peor que el alcohol y el tabaco; no le falta razón: en las plazas de París se reúne gente al borde del suicidio, completamente obsesionada por resolver el enigma.

Ay, ay, ay... Con la de tiempo que he pasado resolviendo problemas ajedrecísticos de Sam Loyd... ¡Aquí se te fue la mano, amigo mío!
En la Oficina de Patentes de San Francisco le pidieron la solución del puzzle, y Sam Loyd en persona dijo ser plenamente consciente de que el problema es insoluble. De hecho, le negaron la patente. Y en el informe consta que se deniega porque "Un acertijo irresoluble carece de utilidad y en consecuencia no puede patentarse".

El problema propuesto, ¿es de hecho imposible? Rotundamente sí. Veamos por qué.

¿Recuerdan las Torres de Hanoi? Se resolvían conservando la paridad del sistema.
La clave, otra vez, es la paridad del sistema formado por todas las fichas.

Tomemos una posición cualquiera de las fichas

y olvidemos que están dentro de un cuadrado, olvidemos que son los elementos de una matriz de 4 filas por 4 columnas; en su lugar, escribámoslos por orden, tal como nos los iríamos encontrando si los recorriésemos con el dedo SIN LEVANTAR EL DEDO y empezando en una esquina CON ficha. Obtendríamos esto:

14 10 15 13 6 3 12 2 9 5 11 8 7 1 4

El hueco está en la esquina: sólo puedo bajar el 8 o desplazar a la derecha el 7. En ambos casos, la secuencia numérica permanece inalterada. ¿Sí?
Luego los movimientos hechos cuando el hueco está en una esquina no alteran la secuencia.

¿Y si el hueco no está en la esquina?

Veamos.
Primero: los movimientos laterales. Es obvio que NO ALTERAN la secuencia.
Segundo: los verticales. El descendente pasa el número que estaba segundo a sexto.
El ascendente pasa el número que estaba noveno a séptimo.

De segundo a sexto. Ambas posiciones son PARES.
De novenos a séptimo. Ambas posiciones son IMPARES. ¡Qué buena pista!

Sigamos.

Sea la secuencia 1 2 3 4. Es la secuencia natural, el orden natural de los números naturales.
Imaginemos que cada número es una ficha sólida.
Imaginemos que la ficha 2 salta por encima de la ficha 1. Tendríamos esta nueva secuencia: 2 1 3 4.
En esta secuencia el 1 y el 2 han invertido sus posiciones. Esta secuencia tiene UNA inversión. Supongamos que ahora la ficha 3 salta por encima de la ficha 4. Tendríamos esta nueva secuencia 2 1 4 3. Están invertidas las posiciones de la pareja 1 2 y las posiciones de la pareja 3 4. Esta secuencia tiene DOS inversiones.

La secuencia 2 1 3 4, por tener UNA inversión tiene un número impar de inversiones. En lenguaje matemático estricto: "la secuencia 2 1 3 4 es una permutación IMPAR de la secuencia original 1 2 3 4".

La secuencia 2 1 4 3, por tener DOS inversiones tiene un número par de inversiones. En lenguaje matemático estricto: "la secuencia 2 1 4 3 es una permutación PAR de la secuencia original 1 2 3 4".

Ejercicio: Calcular el número de inversiones de la secuencia
9 2 5 4 1 6 8 3 7
La solución, al final de la entrada.

Seguimos.
Los movimientos legales (ficha 2ª pasa a 6ª, ficha 9ª pasa a 7ª) alteran el número de inversiones de la secuencia, claro que sí, PERO NO SU PARIDAD.
La inversión que era par sigue siendo par. Y la que era impar sigue siendo impar.

Conclusión: los movimientos permitidos en el "Jeu du Taquin" no alteran la paridad de la permutación del orden inicial de las 15 fichas.

Como la posición que debía alcanzarse para ganar los mil dólares es una permutación par y la posición de partida en que se vendía el juego es una permutación impar, el problema propuesto es imposible de resolver. Y la palabra tramposo está plenamente justificada, aunque en este caso haya que aplicársela a Sam Loyd, cuyos problemas ajedrecísticos contribuyeron a hacer de mí la persona que soy y no otra distinta.

¡Te pasaste de la raya, Sam, hiciste trampa! No mereces la bendición de Caissa, por mucho que llegases a ser el décimoquinto mejor tablero estadounidense de tu época.
Para los que no hacemos trampa ni al parchís, has dejado de ser un referente, Sam, que lo sepas.

Ah, por cierto, este asunto de la paridad... ¿sirve para algo serio, para algo que no sean las Torres de Hanoi o el Taquin?

La verdad es que sí.

Hay gente que se cree que está definiendo qué es un voltio al decir que es un amperio dividido por un ohmio. Igualito, igualito, hay quien se cree que está definiendo qué es un determinante de orden 2 al decir que es el producto del elemento 11 por el elemento 22 menos el producto del elemento 12 por el elemento 21.
Ambos cometen el mismo error: confunden "el concepto" con la operación que nos da el resultado numérico asociado al concepto.

Quien quiera definir correctamente qué es un voltio deberá decir que es la diferencia de potencial existente entre dos superficies equipotenciales de un campo eléctrico creado por una carga puntual cuando el desplazamiento entre las mismas de un culombio requiere un gasto energético de un julio.
Se puede dar una definición correcta basada en circuitos, claro que sí: la diferencia de potencial entre dos puntos de un circuito es un voltio cuando una corriente de un amperio circulando entre ellos disipa un julio por segundo.

¡¡Que no es lo mismo que la Ley de Ohm!!

Igualmente, quien quiera definir con el rigor que merecen los entes matemáticos qué es un determinante deberá decir - ejemplo de definición elegante donde los haya - lo que sigue:

Dada una matriz cuadrada A, llamaremos determinante de A a la suma algebraica de todos los productos que podamos formar tomando uno y solo un factor de cada fila y uno y solo un factor de cada columna, siendo cada producto positivo o negativo según sean respectivamente iguales o diferentes las paridades de las permutaciones de los subíndices primeros y segundos de los factores que lo forman.

Aplicando la definición al caso de orden 2, nos queda la fórmula:

En el primer producto, los primeros subíndices son 1 2 y los segundos son 1 2, la misma paridad, signo positivo.
En el segundo producto, los primeros subíndices son 1 2 y los segundos son 2 1, distinta paridad, signo negativo.

Exactamente igual se justifica la fórmula para orden 3:

Pero la fórmula NO ES la definición.
La operación que nos da el resultado NO ES el concepto.

En general y con la notación de Leibniz:

Vaya, qué cosas, el concepto de paridad sí que servía para algo más que para resolver puzzles, después de todo.



SOLUCIONES:

Solución del problema de ajedrez:
En la posición del diagrama, es más fácil ahogar al rey negro – lo que supone empatar la partida – que rematarlo. 1: Ab8 f2 (única) 2: Tc7 (bloqueando la acción del álfil para que el rey negro pueda moverse en lugar de quedar ahogado) Rh2 (única) 3: Th7++.
Ajedrecistas de alto nivel pueden quedarse un buen rato “empanados” delante de esta posición antes de que se les ocurra Ab8.

Solución del ejercicio:
Respecto al 1, están invertidos (por delante de él) el 4, el 5, el 2 y el 9. Ya van 4 inversiones. Respecto al 2, está invertido el 9. Ya van 5.
Total: 17. Impar.

1: Las Torres de Hanoi.

No hace mucho que ha pasado el 21 de diciembre de 2012, así que aún me chirría en los tímpanos eso de que los mayas habían profetizado para tal fecha el fin del mundo, cuando lo único que habían reseñado para la ocasión era el comienzo de un nuevo ciclo astronómico. Bien calculado, por cierto.
Pero hoy no vamos a territorio maya. Hoy, aunque Hanoi sea una ciudad vietnamita, nos vamos a la India y a Francia.

En Benarés sí que existe una profecía sobre el fin del mundo. En el Templo de Brahma, bajo la cúpula principal, existen tres varillas verticales (hay quien dice que las originales eran de diamante, que queda muy bonito…) clavadas sobre un soporte de madera. Lo habitual es designarlas, de izquierda a derecha, A, B, C. Cuando un monje le preguntó a Brahma durante cuánto tiempo iba a existir el universo, Brahma contestó ensartando en la primera varilla sesenta y cuatro discos de oro por orden de tamaño, siendo el situado en la base el disco de mayor diámetro y el que ocupa la posición más alta el más pequeño.
Brahma dio a los monjes las siguientes instrucciones:

1/ Mover un disco consiste en sacarlo de una varilla y ponerlo en otra.
2/ Sólo podéis mover un disco cada día.
3/ Jamás puede ponerse un disco encima de otro que tenga menor diámetro.
4/ Cuando los 64 discos, ordenados de mayor a menor, estén en la tercera varilla, la cúpula, el templo y el mundo entero desaparecerán.

Esto sí que es una profecía, aunque no tenga fecha explícita.
Para un espíritu matemático, la fecha está implícita en las instrucciones y, por supuesto, la tentación de calcularla es irresistible.

Empecemos por simplificar el problema: ¿cuántos movimientos puedo hacer si el número de discos es cero? Respuesta obvia: ninguno. Ya tenemos una primera pareja de valores: a cero discos corresponden cero movimientos.
Sigamos. ¿Cuántos movimientos puedo hacer con un disco? Poder, lo que se dice poder, puedo hacer infinitos movimientos entre la varilla A y la varilla B, dado que las instrucciones no prohiben deshacer movimientos ya hechos. Pero esa respuesta es muy mala. ¿Por qué? Porque la pregunta era peor aún. Hagamos la pregunta correcta: ¿cuántos movimientos son necesarios y suficientes para alcanzar el objetivo? Muy sencillo: quitamos el disco de la varilla A y lo ponemos en la C: un movimiento.
¿Y si tenemos dos discos? ¿Y si tenemos tres, cuatro...?

La respuesta puede verse en los diagramas adjuntos, que nos llevan a la conclusión (habría que demostrarla para n+1, ya sé, lo pasamos por alto...) de que el número mínimo de movimientos necesarios para completar la tarea es mov=2ⁿ - 1
Lo que, aplicado al caso n=64 nos arroja la cifra de 18.446.744.073.709.551.615.

Dicho de otro modo, si los monjes no cometen ningún error (hecho un movimiento, tienen todo el día para pensarse el siguiente...), la profecía se cumplirá dentro de, lo voy a escribir en notación científica, 5'054.10¹⁶ años.

No hay motivo para alarmarse. Da tiempo a que el Sol consuma todo el hidrógeno disponible, empiece a fusionar helio, se transforme en una gigante roja, evapore a Mercurio, a Venus, a la Tierra junto con la Luna y puede que también a Marte, acabe el helio, se enfríe, se apague y muera.

No hacía falta que Brahma tomase tantas precauciones, eligiendo el número 64. Con la mitad de discos, con 32, bastaba y sobraba. Con 32 discos, la tarea requiere 11767 milenios. Muchísimo más de lo que razonablemente durará la humanidad.

Espera. No hemos dicho ni media palabra de cómo se resuelven las torres de Hanoi, cómo se pasan todos los discos ordenados a la varilla C.

Ni hemos dicho nada de Francia. Esto se arregla rápido: Edouard Lucas, un matemático francés, dijo en 1883 que el juego era invento suyo y lo patentó en su versión de 8 discos, incluyendo la leyenda anterior a modo de introducción para las instrucciones.

Hay quien sostiene que el Templo, las agujas, los 64 discos, existieron realmente en alguno de los miles de templos de Benarés; los monjes, alejados de miradas indiscritas, prosiguen hoy día, quizá, su callada labor.
Y hay quien sostiene que la leyenda es una patraña publicitaria inventada por Edouard Lucas, que solía autoplocamarse "profesor de Siam", para darle al juego un toque exótico y aumentar las ventas.
Sea como sea, si alguien quiere investigar cuál de las dos versiones es la cierta, hasta que se cumpla la profecía tiene tiempo de sobra.

¿Y cómo se resuelve? No perdiendo la paridad del conjunto de discos. Numerando de abajo a arriba, los discos son 1,2,3,4,5,...,n. O sea, impar, par, impar, par, impar, par,...,n.
Si n es par, el primer movimiento debe ser de la varilla A a la varilla C.
Si n es impar, el primer movimiento debe ser de la varilla A a la varilla B.
A partir de ahí, basta con no alterar la paridad del sistema. Dicho en lenguaje coloquial: no pongas nunca un disco par sobre otro par ni un disco impar sobre otro impar y acabarás el puzzle; si en algún momento te es imposible respetar esta regla, es que ya te has equivocado antes.

Como la clave está en no perder de vista qué discos ocupaban inicialmente posición par y qué discos ocupaban inicialmente posición impar, es más fácil resolver este juego

que este otro

En internet hay cientos de simuladores de las torres de Hanoi.
¿Por qué no pruebas?