La potencia del 2 (III)

La potencia del 2 (I)

La potencia del 2 (II)

Termino hoy con una serie de tres entradas dedicada a las potencias del número 2, concretamente a las diversas situaciones en las que aparecen sin que casi nos demos cuenta, y que gracias a sus propiedades podemos explicar y, por consiguiente, entender mejor cómo se puede adivinar el número que ha pensado otra persona sin necesidad de ser un experimentado mago, tal y como os conté en la primera entrada, o cómo se podría alcanzar cualquier altura doblando una hoja de papel varias veces por la mitad, de lo cual os hablé en la segunda entrada. Hoy os voy a mostrar dos nuevos casos protagonizados por las potencias del 2 que, al igual que los cuatro que os he compartido hasta ahora, estoy seguro de que os sorprenderán.

El primer ejemplo que os traigo es un rompecabezas bastante conocido, aunque puede que algunos de vosotros solamente lo conozcáis de oídas. Se trata de las Torres de Hanói, un juego para una única que persona que se compone de un tablero en el que hay fijados tres postes y varios discos de diferente tamaño perforados en su centro que se pueden insertar en dichos postes. El juego consiste en pasar los discos que están apilados de menor a mayor tamaño (mirándolos de arriba abajo) en el primer poste al tercero de tal manera que queden en el mismo orden, para lo cual se puede utilizar el segundo poste como apoyo, teniendo en cuenta que en cada paso se permite mover un único disco a otro poste, que en cada movimiento solamente se puede desplazar el disco situado en la parte más alta de uno de los postes, y que no se puede dejar un disco encima de otro de menor tamaño.

A priori, el juego se antoja sencillo. Veamos a través de varios ejemplos cuáles serían los movimientos que habría que hacer, para lo cual llamaremos D1 al disco más pequeño, D2 al siguiente, y así sucesivamente, y que los postes son P1, P2 y P3:

• Un disco: D1 de P1 a P3.
• Dos discos: D1 de P1 a P2, D2 de P1 a P3, D1 de P2 a P3.
• Tres discos: D1 de P1 a P3, D2 de P1 a P2, D1 de P3 a P2, D3 de P1 a P3, D1 de P2 a P1, D2 de P2 a P3, D1 de P1 a P3.
• Cuatro discos: D1 de P1 a P2, D2 de P1 a P3, D1 de P2 a P3, D3 de P1 a P2, D1 de P3 a P1, D2 de P3 a P2, D1 de P1 a P2, D4 de P1 a P3, D1 de P2 a P3, D2 de P2 a P1, D1 de P3 a P1, D3 de P2 a P3, D1 de P1 a P2, D2 de P1 a P3, D1 de P2 a P3.

Como era de esperar, conforme aumentamos el número de discos, la cantidad de movimientos que hay que hacer es también mayor; de hecho, con cuatro discos ya empiezan a marear tantos números y letras, y cuesta entender qué disco se mueve en cada paso, en qué poste está y a cuál va (espero no haber cometido ningún error al detallar cada paso). Podríamos analizar la secuencia que sigue cada disco para determinar qué movimiento hay que hacer en cada momento, pero no me voy a detener en este aspecto, sino que me centraré en averiguar cuántos movimientos son necesarios para resolver este rompecabezas en función del número de discos de partida.
Para ello, la clave reside en darse cuenta de que, si tenemos N discos, primero tenemos que pasar los N-1 discos más pequeños al segundo poste, luego tenemos que pasar el disco más grande (DN) al tercero, y por último pasar los N-1 discos más pequeños al tercer poste. ¿Qué quiere decir esto? Que el número de movimientos necesarios para resolver las Torres de Hanói con N discos es dos veces la cantidad de movimientos que se necesitan para mover N-1 discos (pasarlos del primer al segundo poste, y pasarlos del segundo al tercer poste) más uno (pasar el disco mayor del primer al tercer poste), tal y como se muestra a continuación, siendo TH(N) el número de movimientos que se necesitan para mover N discos:

• TH(1) = 1 movimiento.
• TH(2) = 2 * TH(1) + 1 = 2 * 1 + 1 = 2 + 1 = 3 movimientos.
• TH(3) = 2 * TH(2) + 1 = 2 * 3 + 1 = 6 + 1 = 7 movimientos.
• TH(4) = 2 * TH(3) + 1 = 2 * 7 + 1 = 14 + 1 = 15 movimientos.

Podéis comprobar que las cantidades indicadas coinciden con los correspondientes números de movimientos que se detallaron anteriormente en cada caso. Ahora bien, existe una forma mucho más rápida y directa de obtener el número de movimientos que se precisan para mover N discos, pero antes de desvelarla quiero que intentéis descubrirla vosotros. ¿Cómo sigue la sucesión numérica 1, 3, 7, 15... y cuál es el criterio que se utiliza para continuar dicha sucesión? Quizás te cueste encontrar la respuesta, pero creo que si te hago la siguiente pregunta ya podrás hallarla. ¿Cómo sigue la sucesión numérica 2, 4, 8, 16... y cuál es el criterio que se utiliza para continuar dicha sucesión? En efecto, ¡son las sucesivas potencias de 2! Entonces, esto quiere decir que el criterio que se aplica en la sucesión 1, 3, 7, 15... es el anterior de cada potencia de 2, o lo que es lo mismo, que para resolver las Torres de Hanói con N discos hay que hacer 2^N - 1 movimientos, una expresión que, al contrario que la que vimos antes, no depende de la cantidad de movimientos necesarios para mover N-1 discos, sino únicamente del número N de discos de partida. En la siguiente tabla podéis visualizar cuántos movimientos serían necesarios para distintas cantidades de discos:

Fijaos en que para 10 discos ya se necesitarían más de mil movimientos, para 20 discos superaríamos la barrera del millón de movimientos, mientras que para 40 habría que mover los discos más de un billón de veces. Y todavía no he terminado de contaros la leyenda que está asociada a este rompecabezas, y es que según parece en un templo budista (supuestamente en Hanói, la capital de Vietnam, de ahí el nombre) hay un grupo de monjes que lleva varios años moviendo 64 discos del primer poste al tercero siguiendo las reglas que he mencionado antes, de tal manera que el mundo se acabará cuando el juego se haya completado. ¿Y queda mucho para eso? Vamos a calcularlo. Ya sabemos cómo obtener el número de movimientos que harían falta, 2^64 - 1 en este caso, es decir, 18.446.744.073.709.551.615 para ser más exactos. Si suponemos que los monjes tardan un segundo en mover un disco, el número total de segundos que tardarán coincidirá con el número de movimientos, pero mejor dividiremos esa cantidad entre 86.400, que son los segundos que tiene un día, y la cantidad resultante entre 365 para determinar cuántos años necesitarán. Pues resulta que tardarán algo más de 584.942.417.355 años, o sea, más o menos 42 veces la edad del universo. Así pues, podemos estar tranquilos que el mundo todavía no se va a acabar, al menos de esta forma.

Vamos con el segundo ejemplo de hoy, que al mismo tiempo es el último que os voy a contar en esta serie de entradas, y el objetivo del mismo va a ser responder a la siguiente pregunta: ¿cuántos antepasados tenemos? Ya os adelanto que es imposible encontrar una respuesta exacta porque no existe un registro de todas las personas que han habitado el planeta ni la relación existente entre ellas, pero lo que sí podemos hacer es estimar cuántas personas nos han antecedido para que cada uno de nosotros haya podido nacer.

Está claro que cada persona tiene dos progenitores (un padre y una madre), cuatro abuelos (dos por parte del padre y otros dos por parte de la madre), ocho bisabuelos (dos por parte del abuelo paterno, dos por parte de la abuela paterna, dos por parte del abuelo materno y dos por parte de la abuela materna), dieciséis tatarabuelos, etc. De aquí se deduce que dicha persona tiene dos antepasados hasta la primera generación (los padres), seis antepasados hasta la segunda generación (los dos padres y los cuatro abuelos), catorce antepasados hasta la tercera (los dos padres, los cuatro abuelos y los ocho bisabuelos), treinta hasta la cuarta, y así podríamos seguir avanzando varias generaciones para esa persona a través de su árbol genealógico, que es la forma en la que representamos gráficamente a los que le antecedieron. La sucesión que se obtiene es 2, 6, 14, 30..., cuyo criterio para continuarla no es demasiado evidente, pero si dividimos entre 2 cada término quedaría la sucesión 1, 3, 7, 15..., que es la que obtuvimos en el ejemplo de las Torres de Hanói, luego la expresión 2 * (2^N - 1) es la que nos permite determinar cuántos antepasados hemos tenido contando las primeras N generaciones. ¡Vaya! Aquí están otra vez las potencias del 2.
Otra cosa que podemos hacer para complementar lo que acabamos de deducir es estimar cuándo nacieron los ascendientes de cada una de esas generaciones teniendo en cuenta que el tiempo que separa a cada generación depende de a qué edad fueron padres los progenitores de una persona, la cual es bastante variable y se ve afectada por diversos factores (etapa histórica, conciliación de la vida familiar y laboral, rasgos culturales y religiosos...), pero para facilitar los cálculos vamos a suponer que la diferencia generacional media es de 30 años. De esta forma, si un bebé nace en la actualidad (2020), sus padres habrán nacido en 1990; sus abuelos, en 1960; sus bisabuelos, en 1930; sus tatarabuelos, en 1900; y así sucesivamente. En la siguiente tabla podéis escrutar la estimación del año de nacimiento de diversas generaciones y cuántos antepasados tendría en total alguien que naciese este año:

Si retrocedemos diez generaciones, en total habrían vivido más de 2.000 personas que han posibilitado que haya nacido una persona este año, pero si viajamos hasta los comienzos del segundo milenio, entonces esa cifra aumenta hasta superar los 2.000 millones de personas, y si nos vamos al año 820, resulta que serían más de dos billones de personas, y si... ¡Espera, espera! Aquí hay trampa, y espero que a estas alturas ya te hayas dado cuenta de que algo está fallando. La población mundial está cerca de alcanzar la barrera de los 8.000 millones de habitantes, y, según diversas estimaciones, se cree que a lo largo de toda la historia son algo más de 100.000 millones de personas las que han habitado el planeta. ¿Cómo es posible que las cantidades de la tabla sean ciertas? ¿Me he equivocado al hacer las cuentas o es que la expresión que deduje antes es errónea? La expresión 2 * (2^N - 1) es correcta y las cuentas están bien hechas (con ayuda de la calculadora), pero esas cantidades son falsas.
Resulta que los valores de la tabla no son cantidades reales, sino cotas muy superiores del número de antepasados que tiene cada persona, ya que no hemos tenido en cuenta que buena parte de los ascendientes se repiten, lo cual reduce una barbaridad esas cantidades, y para que lo entendáis os voy a poner un ejemplo. Pensad en vuestro padre y en vuestra madre, dos personas que a priori no guardan ningún parentesco familiar, pero podría ocurrir que ambos procedan de una misma pareja de ocho generaciones anteriores que tuvo dos hijos (que pertenecerían a la séptima generación), de tal manera que de uno de ellos acabaría naciendo vuestro padre, y del otro vuestra madre. He dicho ocho generaciones por decir una cantidad, igualmente podría haber dicho quince o cuatro, que tampoco es muy descabellado, sobre todo en determinadas localidades o zonas poco comunicadas en las que hay muchos vínculos familiares; si no, imaginad el típico pueblo de 300 o 400 habitantes perdido entre montañas cuyos habitantes apenas salen de allí, al final se acaban casando primos segundos o terceros.
Volviendo al ejemplo, tendríamos entonces que vuestros padres serían familia, lejana eso sí, pero lo suficiente como para que el número de total de antepasados disminuya considerablemente, y si tenemos en cuenta que en ese mismo árbol genealógico se entrelazan varios casos más, entonces resulta que acaban surgiendo muchos más ascendientes comunes que estaríamos contando por partida doble, triple, cuádruple, etc. Por lo tanto, no, cada uno de nosotros no tiene billones y billones de antepasados, sino solamente varios miles o quizás millones, lo cual quiere decir que, de una forma u otra, algunas de las personas de tu entorno diario son familiares más o menos lejanos o cercanos, según cómo se mire.

Pues hasta aquí he llegado. Han sido tres entradas en las que he expuesto seis casos muy diversos entre sí pero con una particularidad que los vincula, y es que en todos ellos hay algo de matemáticas, y para ser más exactos bastante de las potencias del 2. Hemos aprendido a hacer un truco de magia, a no ser víctimas de un timo que no lo parecía, a llegar a la Luna y al Sol doblando un papel, a contar granos de trigo en un tablero de ajedrez, a jugar a las Torres de Hanói antes de que acabe el mundo y a calcular cuántas personas han tenido que vivir para que cada uno de nosotros haya nacido. Todo ello con una operación (la potencia) y un número (el 2). Con muy poco se puede hacer mucho.

Nota: este post forma parte del Carnaval de Matemáticas, que en esta octogésima octava edición, también denominada 11.2, está organizado por Rafael Martínez González a través de su blog El mundo de Rafalillo.