Cadena más larga de 100 números

Le he estado dando vueltas a un problema curioso en http://simplementenumeros.blogspot.com.es/2013/05/1130-los-numeros-del-1-al-100.html. Se trata de formar la cadena más larga posible con los números del 1 al 100, de forma que cada número en la cadena sea o bien múltiplo o bien divisor de sus vecinos.

Una solución es la siguiente cadena de 77 números:

76-38-19-95-5-85-17-34-68-4-92-46-23-69-3-87-29-58-2-62-31-93-1-77-11-99-33-66-22-44-88-8-96-32-64-16-48-24-72-36-18-54-27-81-9-63-21-42-84-28-56-14-98-49-7-35-70-10-80-40-20-100-50-25-75-15-45-90-30-60-12-6-78-39-13-26-52

En realidad hay muchas soluciones con 77 números; por ejemplo, en esta cadena se pueden intercambiar las posiciones de 26 y 52, y de 40 y 80.

La cadena tiene la siguiente estructura:

• 4 múltiplos de 19, y el 5;
• 4 múltiplos de 17, y el 4;
• 4 múltiplos de 23 y el 3;
• 3 múltiplos de 29 y el 2;
• 3 múltiplos de 31 y el 1;
• y finalmente una cadena de 54 números múltiplos de 2, 3, 5, 7, 11 y 13.

Es fácil ver que en la solución no deberían aparecer los primos mayores que 50; 53,59,61,67,71,73,79,83,89 y 97; porque sólo se pueden conectar al 1. Ni tampoco aquellos primos entre 33 y 50 junto con sus dobles, 37 y 74, 41 y 82, 43 y 86, 47 y 94; porque sólo se pueden conectar al 1 y al 2. En cambio, los múltiplos de 17, 19, 23, 29 y 31 sí pueden aparecer, porque son 5 grupos con más de tres números que sólo se pueden conectar al 1,2,3,4,5. Si en la solución apareciese por ejemplo el 37, sería porque alguno de estos primos no aparecería, y por tanto se podría alargar la solución quitando el 37 y poniendo el primo que no estaba.

Aparte de estos 18 números (primos > 50 y primos y dobles entre 33 y 50) que sabemos que no pueden aparecer, hay otros 5 que no aparecen en la solución dada: 51, 55, 57, 65 y 91. El 51 y 47 son múltiplos de 17 y 19 y podrían aparecer, pero entonces tendrían que desaparecer el 85 y el 95.

Así que en realidad sólo se podría mejorar la solución en 3 números. Pero esto no es posible. La cadena larga, a partir del 1, es la más larga posible (demostrado por ordenador). Es verdad que podríamos quitar, por ejemplo, los múltiplos de 31 para dejar libre el 1, con lo cual podríamos enganchar algún otro número. Pero es que en la solución ya hay tres múltiplos de 31; incluso si pudiésemos enganchar los tres números que nos faltan, perderíamos otros 3, con lo cual no mejoraríamos la longitud de la cadena.

Total, que queda por ver cómo encontrar la cadena larga. El problema se puede formalizar como buscar el camino más largo posible en un grafo de 57 vértices. Se podría usar backtracking a lo bruto, pero esto tarda demasiado.

Una primera mejora para podar el árbol es, antes de probar a explorar un nuevo vértice, contar el número de vértices en su componente conexa. Si la componente conexa tiene N vértices, la cadena que ya he explorado tiene longitud L, y de momento el récord de cadena más larga que he encontrado es R, entonces no tiene sentido explorar si N+L <= R, no se podrá batir el récord. Esto mejora una burrada el tiempo de búsqueda, pero sigue siendo lento.

La clave para conseguir explorar todo el árbol de caminos es darse cuenta de que los grafos que quedan por explorar son bastante "fibrosos". Al principio hay unos cuantos números muy conectados, pero tienen a desaparecer pronto y dejar un grafo deshilachado. Por ejemplo, uno que aparece relativamente pronto y que estuve depurando en detalle es éste:

Se entra por el 35. Aunque tiene 21 vértices, está claro que los dos caminos más largos posibles son de sólo 11. Una forma de afinar la cota sería darse cuenta de que en ese grafo hay 6 hojas (vértices con un único vecino) y como sólo podremos usar como mucho uno de ellos (porque ahí se acaba el camino), aunque el grafo tenga 21 vértices podemos acotar los vértices útiles a 21-6+1.

Pero claro, podemos repetir esta observación... en un grafo como éste, si primero quitamos las hojas 21,25,35, nos queda otro grafo con hojas, así que le quitamos 3 y 5 y finalmente nos queda un grafo con 1 vértice sin hojas (15 no es hoja porque está conectado al principio del camino). Así que en ese grafo el camino más largo que podremos recorrer es de 1+2 vértices (1 es el número de vértices en el grafo final y 2 es el número de veces que hemos eliminado hojas).

Acotando de esta forma la longitud del camino máximo dentro de un subgrafo, se puede explorar todo el grafo de 57 vértices en unas 24 horas.

Historias y probabilidades

He estado leyendo un libro, "El andar del borracho: cómo el azar gobierna nuestras vidas". Aparte de la novelesca biografía de Cardano en el capítulo 3, hay una cosa que me ha intrigado.

Imagínate que te pregunto "¿qué es más probable, que a mi empresa le vaya bien el año que viene, o que a mi empresa le vaya bien el año que viene a causa de la recuperación económica mundial?"

Vale, la pregunta es un poco ambigua, y además habría que adornarla un poco y poner otras opciones para que la trampa no sea tan descarada, pero incluso con esta presentación tan chusca, esta pregunta ha desconcertado a varios de mis compañeros de trabajo, varios de los cuales escogieron la segunda alternativa.

Bueno, pues no, la más probable es la primera; siempre que ocurra que a mi empresa le vaya bien _Y_ haya recuperación económica mundial _Y_ la causa de que a mi empresa le vaya bien sea la recuperación económica mundial (tres condiciones), ocurrirá que a mi empresa le irá bien (una condición).

Esta observación debería de ser obvia, pero la gente cae en ella con facilidad en cuanto la trampa se disimula un poco. Cuando quieres convencer a alguien de algo improbable, en vez de analizar las cosas, lo que tienes que hacer es contarle una historia. Esto lo saben perfectamente los abogados que tienen que convencer a un jurado de algo que normalmente resultaría obviamente falso; se inventan una historia en la que cada paso conecte con el siguiente, y así consiguen esquivar la capacidad de la gente de estimar si algo es creíble o no. Eso sí, no intentes esto con el juez: el profesional pasará de tus milongas y mirará el informe de balística. Así es como funcionan también las conspiranoias.

Otro problema chulo de grafos

Hace tiempo leí otro de esos problemas chulos de grafos sin datos, vagamente parecido al que ya conté de los señores Mancha, aunque este es más fácil.

Resulta que en una fiesta los invitados cumplen la siguiente propiedad más bien especialísima: para cada par de invitados, existe exactamente un invitado al que conocen los dos. Pregunta: ¿cómo es la fiesta?

Formas de montar una escena

Un amigo mío que es director de películas me contó intrigado el siguiente problema. En un libro sobre composición, donde querían enfatizar lo complicado que puede ser montar una escena, contaban que si tienes n tomas, entonces puedes montarlas de N=e·n!-1 formas diferentes para construir la escena, lo cual implica que habrá tantas posibilidades de hacerlo que no será nada fácil decidir entre ellas.

Un ejemplo para aclarar el problema. Quieres mostrar una fiesta en una habitación y tienes cinco tomas; en ellas, la cámara enfoca la puerta, un sofá, el balcón, la mesa con la comida, y la pista de baile. Podrías desechar algunas tomas, o usar sólo un trozo de alguna toma, pero claro, tienes que usar al menos una toma.

¿De cuántas formas se puede hacer esto? Se podrían usar las 5 tomas, mostrándolas ordenadas de 5!=120 formas diferentes. También se podrían usar cuatro tomas; se podrían escoger de comb(5,4)=5 formas, y para cada elección, las tomas seleccionadas se podrían mostrar ordenadas de 4!=24 formas diferentes. O tres, o...

En términos matemáticos, se quiere el número de permutaciones de subconjuntos no vacíos de un conjunto de n elementos.

En total,

Así que la fórmula es rara pero correcta, al redondear el resultado al entero más cercano dará la respuesta correcta.

Ese -1 es peculiar. Sería raro que te preguntasen qué permutaciones hay en el término e·n!. Sin embargo, está muy claro cuál es la permutación que no hay en el -1: la del conjunto vacío.