El Blog de Adrián Paenza

Para conmemorar los 20 años de la caída del muro de Berlín, el gobierno alemán organizó una exhibición en la que hacían una fila de unos mil enormes bloques generando un efecto dominó: Lech Walesa empujó el primer bloque de la fila, éste cayó empujando la siguiente, que cayó empujando el siguiente, y así fueron cayendo todos los bloques, uno a uno.
La caída de los bloques, que habían sido pintados por artistas de todo el mundo, simbolizaba la caída del muro que hasta 1989 separaba Berlin en una zona Occidental y otra Oriental. Pero también transmitía la idea de que aquella caída del muro fuese el primer bloque que generara una reacción en cadena de la caída de otros muros que pueda seguir habiendo en el mundo.

Las exhibiciones de efecto dominó son muy usuales en algunos países, que incluyen concursos en los que una y otra vez se bate el récord de cantidad de piezas de dominó usadas y que ya se cuentan por millones.

 

 

El efecto dominó parece pensado como la representación visual del principio de inducción completa, una forma de razonamiento sumamente útil y poderosa de la matemática.

¿En qué consiste el principio de inducción completa? Imagine que tiene que transmitir un mensaje a un gran grupo de personas que se encuentra formando una larga fila, que se extiende hasta el infinito, y para lograrlo piensa en el efecto dominó.

Para estar seguro/a de que cada una de las personas de la fila se enterará del mensaje que usted quiere transmitir tienen que suceder dos cosas:

• Usted tiene que transmitirle el mensaje a la primera persona de la fila, y
• Tiene que estar seguro de que quien conozca el mensaje se lo pase al siguiente de la fila.

El principio de inducción completa es la traducción a la matemática de estas dos pautas. En matemática, muchas veces se tiene que demostrar que una fórmula “funciona” para todos los números naturales (es decir 1, 2, 3, ...). La forma de lograrlo, apelando al principio de inducción completa, es la siguiente:

• Asegúrese de que la fórmula “funciona” para el primer valor de la lista, el 1.
• Compruebe que si la fórmula “funciona” para algún valor, entonces también “funcionará” para el siguiente.

Si usted puede cerciorarse de estas dos cosas, ¡listo!
Por el primer punto, la fórmula funciona para el 1.
Por el segundo punto, como la fórmula funciona para el 1, entonces funcionará para el 2.
Por el segundo punto nuevamente, como la fórmula funciona para el 2, entonces funcionará para el 3.
Y así siguiendo.

 

 

Con esto usted se asegura de que el mensaje llega a todos los que están en la fila, pero pensemos ahora un problema relacionado.
Las mismas personas se encuentran en la misma fila, y ya conocen la "lógica inductiva" del ejemplo anterior.
En cierto momento, a una de ellas (que está en el lugar N de la fila) se le presenta un problema que necesita resolver. ¿Qué hace? Le pregunta al que está antes que él en la fila (es decir, en el lugar N-1), que le dice “Yo te lo arreglo, pero ¿me esperás un momento?”, con lo que nuestro amigo (el del lugar N) se queda tranquilo y esperando.
Resulta que esta otra persona (N-1) tampoco sabe bien cómo resolverlo, pero como se encuentra en la misma situación en la que el otro (N) estaba al comienzo, apela al mismo truco: le pregunta al que está antes que él en la fila (N-2), que le dice lo mismo: “Yo te lo arreglo, pero ¿me esperás un momento?”.
Uno ya se imagina cómo sigue la cosa. Cada uno desconoce cómo resolver el problema que le presentan, pero le pregunta al anterior, que le asegura que le va a arreglar el problema (siempre que se le tenga algo de paciencia). Esta cadena "en reversa" continúa hasta el primero de la fila (el del lugar 1), que sí sabe la respuesta al problema que le plantean. Toda la cadena se reconstruye entonces hacia el otro lado, hasta el que preguntó primero (N) que logra así resolver su problema original.

Como vemos, este mecanismo es la otra cara de la moneda del método de inducción completa, ya que se basa en un replanteo de las mismas dos reglas:

• Cada uno de los que está en la fila piensa “si el que está antes que yo supiera resolver el problema, me lo diría y entonces yo también sabría resolverlo”.
• Y, además, el primero sabe la respuesta.

Este es un caso particular de lo que en matemática se llama recursión: la descomposición de un problema en otro/s más simple/s (aunque no es necesario que el nuevo problema sea similar al original).

 

 

La inducción completa y la recursión están presentadas aquí muy de manera muy simplificada, pero mostrando cómo en una y otra subyace una idea muy fuerte y muy usada en la resolución de problemas: aprovechar problemas más pequeños (o distintos) para resolver problemas más grandes.
Cuando un problema es muy grande, puede ser útil analizar casos similares pero más pequeños, o variantes del problema original. Las conclusiones que uno obtiene en ese análisis podrá eventualmente extrapolarlas y vincularlas después nuevamente a ese problema original.
En la inducción, y muchas veces en la recursión, el vínculo entre los casos pequeños y los grandes está claramente organizado mediante un encadenamiento "paso a paso" a través de los números naturales.

Ahora, y con estos métodos a la vista, ¿se le ocurre alguna nueva forma de pensar el problema de la isla de los lógicos perfectos?