Tras la semana de rigor, ya tenemos las soluciones al desafío del Encuentro estelar que os planteamos el sábado pasado. Por los correos recibidos, parece que habéis disfrutado bastante con él, ¡estupendo! Eso sí, antes de ir a las respuestas finalistas y ganadora, una disculpa.

Mi intención era plantear una primera pregunta relativamente fácil, una segunda más difícil y una tercera aún más difícil. Sin embargo, metí la pata al hacer de la primera pregunta el caso de una galaxia de 10x10 sistemas, porque resolver ése requería prácticamente resolver la segunda pregunta… hacer el 10x10 a mano es horrible. De modo que tenía que haber hecho de la primera pregunta un caso 4x4 o algo así, para dar un primer paso resoluble sin llegar a la fórmula genérica. Con lo que, en la práctica, se trataba de un desafío de dos preguntas y ninguna de ellas era tan fácil como me hubiera gustado, ¡lo siento!

Los finalistas han sido César, Javier y Alberto, y el ganador ha sido Felipe. Pero, antes de ir con las soluciones correctas, una aclaración sobre una incorrecta pero que ha sido bastante común.

Es cierto que los dos escuadrones van a encontrarse en la diagonal del cuadrado, en la que hay –en el caso 10x10– diez posibles sistemas de encuentro. De ahí no es correcto deducir que, ya que las naves pasan por un sistema de diez posibles, la probabilidad es 1/10 de encontrarse. Eso sería cierto si los diez sistemas fueran equiprobables, pero no lo son. Si se hacen las cosas paso a paso, como veremos en un momento en alguna solución correcta, se hace evidente que es mucho más probable el paso y el encuentro en los sistemas cerca del centro de la diagonal, y muy improbable cerca del extremo, simplemente porque hay muchas maneras de alcanzar el centro y pocas de alcanzar un extremo, al moverse aleatoriamente.

Mejor que yo lo explica uno de los finalistas, César. No os perdáis el dibujo, en el que pueden verse los posibles sistemas a los que puede haber llegado la nave en cada salto, junto con su probabilidad. Creo que viendo esto se abrirán los ojos de quien respondió 1/10:

---

Comenzaré calculando directamente el caso de NxN sistemas, el caso N=10 solo será un caso particular. Utilizaré conceptos matemáticos de nivel medio como sumatorios, factoriales o combinatoria, las explicaré muy por encima.

Para empezar, nos centraremos en la nave roja, nos olvidamos por ahora de la azul. Nuestro objetivo es calcular las probabilidades en cada punto del mapa y en cada instante. Es bien simple:

• En el primer movimiento (día 3), la nave tiene solo dos posibilidades, serán por tanto un 50% (1/2) de probabilidad para cada sistema que la nave se encuentre allí.

• En el segundo movimiento, (día 6), la nave se puede mover a tres sistemas (ver dibujo), sin embargo, la probabilidad no es la misma para los tres sistemas. Explicándolo de una manera un poco burda, el primer 50% de probabilidad (del día 3) del primer sistema se reparte por igual (25%, 1/ 4 ) entre sus dos inferiores, al igual que el otro. De ahí que el primer y tercer sistema del día 6 solo tenga un 25% (solo ha intervenido el sistema del día 3 superior en cada caso). Mientras que el segundo sistema del día 6 tiene un 50% de probabilidades al venirle de cada uno de los dos sistemas superiores un 25%.

• El día 9 es igual, fijarse en el dibujo para una mejor compresión.

He dibujado el sistema en forma de “pirámide”, enseguida se verá su utilidad. Primero nos fijamos en cada línea horizontal verde, cada una corresponde a un día determinado, la nave por tanto ira bajando hacia abajo con el transcurso de los días. Obviamente, si sumamos los porcentajes de cada línea obtenemos 1 (100%) de probabilidad.

Ahora pondremos nuestra atención en los denominadores (números de debajo de las fracciones). Se mantiene constante en cada fila pero conforme vamos bajando, este se multiplica por dos, por tanto tiene un crecimiento de la forma 2n donde “n” representa el número de la fila empezando desde 0.

En el caso del numerador (número de arriba de la fracción) parece más complicado encontrarle una regla, sin embargo nos encontramos ante el mismísimo “triángulo de Tartaglia/Pascal”. Para aquellos que aún no lo conozcan se forma de la siguiente manera:

Empezamos escribiendo un uno arriba del todo y en las dos diagonales en sentido descendente a ambos lados del 1. Ahora empezamos a escribir en la primera casilla vacía la suma de los dos números superiores (1+1). Una vez acabada esa fila, pasamos a la siguiente, serán (1+2) siendo “1” y “2” los dos números superiores y así sucesivamente.

Esta construcción matemática tiene muchos usos, como por ejemplo para calcular el desarrollo de (a+b)n (binomio de Newton) de forma rápida o para combinatoria. Recomiendo para aquellos que no lo conozcan una lectura más detalla de él en Wikipedia o en cualquier otro sitio.

Cada número del triángulo se puede calcular mediante:

Donde “n” representa a cada fila, y “p” a cada diagonal (ver primer dibujo). Para más información sobre esta fórmula buscar sobre: “coeficientes binominales”.

En estas condiciones, ya somos capaces de dar una fórmula matemática para la probabilidad en tanto por 1 en cada sistema solar. Esta es:

Después de todos estos preliminares pasaremos a resolver el problema.

• Las dos naves coincidirán (o pueden coincidir) en una horizontal (líneas verdes), llegando las dos a la misma vez a dicho sistema.

• Si la probabilidad de que la primera nave se encuentre en una determinada posición es x1 y la de la segunda nave en el mismo punto es x2 la probabilidad de que coincidan ambos sucesos es: “X1·X2”

• Por lo tanto, la posibilidad de que se encuentren ambas naves es la suma (sumatorio) de las posibilidades de encuentro en toda esa línea.

• Como ambas posibilidades son iguales, tendremos:

Posibilidad total =

(El sumatorio continua hasta “P - a = 0 “)

Por ejemplo, si tomamos el problema primero de un casillero 10x10, tendremos un n=9 (al existir n=0), existirán 10 términos en el sumatorio cada uno correspondiente a la probabilidad de encontrarse en cada punto posible.

---

Puedes leerla entera aquí: Solución de César. Como veis, él alcanza la solución general para un cuadrado de NxN, aunque no responde a la pregunta concreta de la probabilidad en el caso N=10. Sí lo han hecho, llegando a fórmulas muy parecidas, otros participantes en el desafío, como Oldman, Fernando, Tamara, Javier, etc. Si realizas los cálculos en la fórmula de arriba verás que resulta ser de aproximadamente 18,5%.

Sin embargo, hay una fórmula general más elegante que los sumatorios a los que habéis llegado casi todos… pero para llegar a ella hace falta plantearse los casos favorables de un modo ligeramente diferente. Así lo ha hecho el ganador del desafío, Felipe, que responde además a las tres preguntas. Creo que, para entender la solución de Felipe (que no incluye imágenes, con lo que requiere de mayor abstracción) hace falta haber entendido antes el razonamiento de César y similares.

La clave de la “mejora” respecto a las soluciones sumadas –aunque Felipe la menciona en su texto, creo que es bueno hacer énfasis en esto– es “viajar hacia delante en el tiempo” para una flota hasta el punto de encuentro, y “hacia atrás en el tiempo” en el caso de la otra flota, para llegar al cálculo de los casos favorables de un modo más sencillo que el sumatorio. El resultado numérico resulta ser el mismo que el de la solución “tipo César”, pero como veréis, la fórmula es más concisa y, en mi opinión, elegante. Dejo que lo explique el propio Felipe, y de paso que responda a la tercera pregunta:

---

Problema 1

Para llegar a la capital enemiga por el camino más corto cada flota tendrá que realizar 18 tránsitos. Los posibles encuentros, si ocurren, serán en la diagonal a mitad de camino, cuando ambasflotas hayan realizado 9 tránsitos.

Para cada tránsito que las flotas realizan en su camino hacia la diagonal, tienen dos posibles caminos que pueden seguir con la misma probabilidad. En el dibujo uno de los caminos es horizontal y el otro vertical.

Como cada uno de los caminos tiene la misma probabilidad, para calcular la probabilidad de un encuentro bastará con contar todos los caminos posibles que pueden seguir las flotas, y de estos aquellos que son favorables para un encuentro entre las flotas. La probabilidad del encuentro será el cociente entre el número de casos favorables y el número de casos posibles.

Empezaré por contar los casos posibles. Como los caminos que sigue la flota escarlata es independiente del de la azul, el número de casos posibles es el número de caminos que puede seguir la flota escarlata en 9 tránsitos multiplicado por el número de caminos que puede seguir la flota azul en otros 9 tránsitos.

Para llegar a la mitad del camino, la flota escarlata realiza 9 tránsitos y en cada tránsito tiene dos posibilidades, el camino horizontal y el vertical, es decir, que en cada tránsito se multiplica por dos el número de posibilidades. El número de caminos que puede seguir la flota escarlata después de hacer 9 tránsitos es de 29. Lo mismo para la flota azul.

Multiplicando:

Casos posibles = 218.

Vamos ahora a por los casos favorables. Hay varios trucos que nos facilitarán la cuenta.

Primero sigamos a la flota roja hata el punto de encuentro, y desde allí sigamos, hacia atrás en el tiempo, el camino que ha seguido la flota azul desde su capital. El resultado es un camino que nos lleva desde una capital hasta la otra con 18 tránsitos en total. Recíprocamente cualquier camino que lleve desde una capital a otra nos da un camino para la flota escarlata y otro para la flota azul en el que las dos flotas se encuentran. Así que para contar los casos favorables nos basta con contar todos los caminos diferentes que llevan de una capital a la otra.

Segundo, un camino que lleva de una capital a la otra tiene 9 tránsitos horizontales y 9 verticales.

Tercero, fijémonos en los tránsitos horizontales. Podemos numerarlos por el número de tránsito al que corresponden, en total 9 números diferentes que van del 1 al 18. Recíprocamente cualquier combinación de 9 números diferentes del 1 al 18 nos da un camino entre las capitales. Basta con que los números correspondan a los tránsitos horizontales y el resto de los tránsitos sean verticales.

Para contar todas las comibnaciones de 9 números diferentes que van del 1 al 18 utilizamos combinaciones sin repetición de 18 elementos tomados de 9 en 9, C(18; 9).

Ahora divido los casos favorables entre los casos posibles y obtendré la probabilidad de encuentro, esto es

o bien un 18,55% de probabilidad.

Problema 2

El método de cálculo es generalizable a cualquier tamaño de galaxia. Para una galaxia N X N el número de tránsitos hasta la diagonal es N - 1 y el número de tránsitos hasta la capital enemiga 2N - 2). Por lo demás se repite el mismo cálculo de probabilidad.

Problema 3

A partir de aquí las expresiones matemáticas que me salen empiezan a ser más largas y desagradables. Habrá alguna solución más simple?

Voy a empezar por el caso 10x10 para explicar el método antes de embarrarme con fórmulas más generales. Las dos capitales están separadas por una distancia de 18 tránsitos. Sabemos que la flota escarlata vuela 3 veces más rápido que la azul, de modo que en el día 12 la flota escarlata ha hecho 12 tránsitos y la flota azul 4. Todavía están a dos tránsitos de distancia. En el día 13 la flota escarlata ha hecho un nuevo tránsito y la azul se ha puesto en camino para realizar un quinto tránsito, pero todavía no se han podido cruzar porque estarán a dos tercios de tránsito de distancia. En el día 14 es el que tienen la oportunidad de encontrarse en pleno tránsito o pasar de largo si han elegido un camino diferente. Para la flota escarlata será el transito número 14 y para la azul el número 5.

El cálculo de la probabilidad será similar, un conteo de casos favorables y de casos posibles. Los casos favorables son los más fáciles porque no va a cambiar prácticamente nada respecto del problema 1. En los casos en los que hay encuentro, podemos seguir a la flota escarlata hasta el planeta o el tránsito en el que haya un encuentro y luego seguir hacia atrás en el tiempo a la flota azul hasta su base. Nuevamente tenemos una correspondencia uno a uno entre caminos en los que se da un encuentro entre las flotas y caminos que lleven de una base a otra. Podemos repetir la misma fórmula del problema 1.

Pasando ahora a los casos posibles, podemos multiplicar nuevamente el número de caminos diferentes que puede seguir la flota azul en 5 tránsitos por el número de caminos diferentes que puede seguir la flota escarlata en 14 tránsitos.

El cálculo del número de caminos que puede seguir la flota azul es igual de fácil que en el problema 1. En todos los tránsitos hay dos posibles caminos, el horizontal y el vertical. En total 25 caminos.

Para la flota escarlata la cosa cambia. Ahora hay 14 transiciones, pero no siempre hay dos caminos para elegir. A veces solo hay uno disponible. Si miramos cuántos trayectos horizontales puede seguir la flota, encontramos que cualquier número entre 5 y 9. Veamos por ejemplo como calcular cuantos caminos posibles hay con 5 trayectos horizontales y 9 verticales. En ese caso tomando los números de transición que corresponden a los trayectos horizontales tenemos 5 números del 1 al 14. Si calculamos todas las combinaciones de estos números tendremos C(14; 5). Pero además habrá que sumar los casos en los que hay 6, 7, 8 y 9 trayectos horizontales. El número total de caminos que puede tomar la flota escarlata es

Multiplicando por el número de caminos que podía coger la flota azul ya tenemos el total de casos posibles.

Y la probabilidad del encuentro

Para la galaxia más general, de tamaño N X N, el método de cálculo es el mismo pero con expresiones algo más complicadas.

Primero tengo que calcular el número de tránsitos TA que realiza la flota azul y el número de tránsitos TS que lleva a cabo la flota escarlata. Para eso utilizaré una función techo(x) que aplicada a un número real positivo, devuelve el propio x si es entero o el entero inmediatamente superior si no lo es.

Los factores 1 y 3 son las velocidades relativas de las dos flotas y el denominador 4 es la suma de las dos velocidades.

El cálculo sigue la misma línea que el del caso 10 x 10.

Casos favorables = C(2N - 2;N - 1);

Número de caminos posibles de la flota azul = 2TA;

Número de caminos posibles de la flota escarlata:

y la probabilidad de que haya un encuentro:

---

Podéis leer la solución en PDF, con un formato probablemente más agradable, aquí: Solución de Felipe. Creo que, aunque sus resultados son elegantes, la explicación podría ser más clara; como seguro que algunos de los que llegásteis al sumatorio podéis entender su mejora respecto a él, si otros tienen dudas podréis ayudarlos en comentarios –como también podrá hacerlo, seguramente, el propio Felipe–.

Finalmente, no puedo dejar de compartir con vosotros un par de soluciones más que, aunque no alcanzan los resultados de Felipe, son muy interesantes u originales. La de Javier es inefable, mejor que te la explique, la lees tú. La de Alberto tiene una representación gráfica muy interesante, y merece la pena echarle un ojo para disfrutar con cosas como ésta:

Como siempre, los finalistas y el ganador podéis contar con el número de octubre de la revista, para que podáis tener vuestras soluciones “en público”. Prometo que en el próximo desafío las preguntas estarán más escalonadas en dificultad, si es que hay más de una… como siempre, ha sido un placer maltratar vuestras decadentes neuronas. ¡Hasta el próximo desafío!