¿Qué de malo podría ocurrir si decidieras participar en el sencillo juego en el que se involucraron animosos los hipotéticos personajes del acertijo que presentamos en esta ocasión?
Seguro que no pasará de un breve dolor de cabeza, pero recompensado con buen aprendizaje.
ACERTIJO
¡Pónte a prueba e inténtalo!
Esperamos con gusto tus comentarios y propuestas, ya sea aquí mismo o a través de los perfiles de Instagram, Twitter o Facebook de The Mexico News e, inclusive, por el chat de Telegram. No dudes en participar.
SOLUCIÓN
Al abordar cuestiones como estas, será siempre útil trazar algunos esbozos con el fin de descubrir algún patrón de repetición.
Quizás incluso algunos lectores se vean tentados, al menos en un principio, a delinear cuantos caminos puedan pero, tal y como atestiguaremos en breve, la tarea es, cuando menos, colosal.
Tableros de \,2\times2\, y \,3\times3\,
En nuestro propósito por hacer un recuento de las posibles vías, conviene sustituir el cuadriculado por una red bidimensional de puntos que coincidan con los vértices de los cuadros que conformaban el patrón original.
Si el cuadriculado tiene dimensiones de n\times n\,, la red contendrá \left(n+1\right)\times\left(n+1\right)\, puntos equiespaciados. Por ejemplo, un arreglo de 2\times 2\, tendrá asociada una red de 9 puntos (véase la Fig. 1)
Por claridad, rotularemos cada uno de estos a la usanza de los elementos de las matrices. El primero de los subíndices se referirá a la fila, mientras que el segundo, a la columna; v. g., dada una matriz cuadrada M, el elemento M_{0,2} es el que se encuentra el la fila 0 y en la columna 2.
Aquí nos hemos decantado por iniciar los valores de los índices en 0, como es común entre los informáticos, en lugar de principiar en 1, que es la notación preferida por quienes se dedican a las ciencias exactas. Esta elección, claro está, no altera en manera alguna los resultados.
Fig. 1 – Retículo bidimensional correspondiente a un cuadriculado de 2\times2.
Una vez construida la red, un diagrama de árbol puede resultarnos clarificador. Teniendo presente que tras partir de M_{0,0} solo son posibles los movimiento hacia la derecha o hacia abajo, las únicas posibilidades son las que siguen:
Fig. 2 – Dendrograma para el tablero de orden 2.
Podemos hacer lo mismo para un tablero de 3\times3,
Fig. 3 – Retículo bidimensional correspondiente a un cuadriculado de 3\times3.
El número de caminos asciende ahora a 20, tal y como se detalla en el diagrama:
Fig. 4 – Dendrograma para el tablero de orden 2.
Definidas las rutas, podemos proceder a dibujarlas
Fig. 5 – Posibles caminos en un tablero de 3\times3.
Sin duda, esto se vuelve impráctico y engorroso para tableros de orden superior, pues el número de rutas comienza a acrecentarse con celeridad. Por ejemplo, para \,n=4\,, son 70 los caminos posibles y para \,n=5\,, la cuantía suma 252.
No obstante es aquí cuando la combinatoria puede venir en nuestro axulio.
El caso general
A primera vista no hemos descubierto una relación de utilidad aún, pero esto dará un giro si advertimos que para completar el recorrido se requieren \,2n\, desplazamientos (\,n\, horizontales y \,n\, verticales), tomados en grupos de \,n\,.
Existen números que describen a la perfección esta situación: los números combinatorios.
Sin mayores pormenores, llamaremos número combinatorio \,m\, sobre \,r\, a la expresión
\begin{equation}
\binom{m}{r}=\displaystyle\frac{m!}{\left(m-r\right)!\,\,r!}\phantom{xxx}\text{con}\phantom{xxx}m,r\in\mathbb{N}_0
\end{equation}Como hemos ya expuesto, este da cuenta de la forma de combinar \,m\, elementos tomados de \,n\, en \,n\,.
Luego, para el caso que nos ocupa la cantidad buscada vendrá dada por
\begin{equation}
\begin{array}{rclcl}
\displaystyle\binom{2n}{n}&=&\displaystyle\frac{\left(2n\right)!}{\left(2n-n\right)!\,\,n!}&=&\displaystyle\frac{\left(2n\right)!}{\,\,\left(n!\right)^2\,}\\
\end{array}
\end{equation}En particular, para \,n=20
\begin{equation}
\begin{array}{rcl}
\displaystyle\binom{40}{20}&=&\displaystyle\frac{40!}{\,\,\left(20!\right)^2\,}\\
\end{array}
\end{equation}Este número le quedará grande a la mayoría de las calculadoras de bolsillo, pero podemos echar mano de software especializado para el cálculo o, también, escribir un pequeño programa en el lenguaje de nuestra preferencia que nos socorra en esta lid. Por ejemplo, usando Wolfram Alpha, obtenemos
\begin{equation}
\begin{array}{rclcl}
\displaystyle\binom{40}{20}&=&\displaystyle\frac{40!}{\,\,\left(20!\right)^2\,}&=&137\,846\,528\,820\\
\end{array}
\end{equation}¡Anda! Hay ciento treinta y siete mil ochocientos cuarenta y seis millones, quinientos veintiocho mil ochocientos veinte posibles caminos. ¡No es conveniente intentar recorrerlos!
Por los siglos de los siglos…
Y, según lo planteado en el enunciado, ¿cuánto demorarían los desafortunados candidatos en esta faena?
Si cada ruta se recorre en 5 segundos, habrán acabado tras
137\,846\,528\,820\cdot 5\text{\,s}=689\,232\,644\,100\text{\,s}Convirtamos esta cantidad a años
689\,232\,644\,100\text{\,s}\times\displaystyle\frac{1\text{ h}}{3\,600\text{ s}}\times\frac{1\text{ día}}{24\text{ h}}\times\frac{1\text{ año}}{365\text{ días}}\cong21\,855\text{ años}Para darnos una idea, si los desdichados hubieran comenzado en el Paleolítico Superior, apenas estarían próximos a terminar.
De aquí se desprende que ninguno de los dos llegó a ser candidato, ni consiguieron la ansiada prebenda.
Saber un poco de matemáticas no le viene mal a nadie antes de embarcarse en tareas que aparentan ser sencillísimas.
