172. (Junio 2019) Marchando una de inducción
Imprimir
Escrito por Pedro Alegría (Universidad del País Vasco)   
Sábado 01 de Junio de 2019

Marchando una de inducciónEl principio de inducción completa es una herramienta matemática tan versátil como intrigante pues permite demostrar infinitas propiedades en solo dos pasos. Para entenderlo, es muy ilustrativo establecer la analogía de este principio con el de la caída de infinitas fichas de dominó (en este video se ven caer un millón de fichas, todavía muy lejos de ser infinitas pero puede servir como aproximación). Como es fácil entender, si numeramos un conjunto infinito de fichas de dominó con los números naturales y los colocamos a una distancia tal que todas las piezas cumplen la condición

"cuando la ficha número n se cae, hace que la ficha número n + 1 también se caiga,"

entonces está claro que, al dejar caer la ficha número 1, las infinitas fichas caerán irremediablemente. No hará falta comprobarlo para la ficha 507 ni para la 4589, ni para ninguna en particular, la condición anterior asegura la caída de todas las fichas.

Esto es precisamente lo que afirma el principio de inducción completa: dada una proposición matemática que depende de un número natural, si queremos asegurar que dicha proposición es válida para todos los números naturales, basta comprobar que es cierta la condición

"cuando la propiedad es cierta para el número n, también será cierta para el número n + 1,"

y, por supuesto, que lo sea también para el número 1.

Marchando una de inducciónA pesar de su aparente simplicidad, este principio ha resuelto multitud de problemas matemáticos de todo tipo, incluso es el fundamento de otras técnicas como el método del descenso infinito, muy utilizado en demostraciones clásicas. Sin embargo, a veces nos puede engañar si no observamos con atención todos sus detalles. El gran maestro George Pólya, en el primer volumen de su libro "Mathematics and plausible reasoning" (Princeton University Press, 1954) propone una paradoja que hoy se conoce como teorema de los caballos o de las niñas rubias:

Dado un conjunto de niñas rubias, si al menos una de ellas tiene los ojos azules, entonces todas las niñas tienen los ojos azules.

La versión original con caballos afirma que todos los caballos son del mismo color.

La demostración es la siguiente:

Es evidente que la afirmación es cierta si el conjunto está formado por una sola niña. Supongamos ahora que la afirmación es cierta para cualquier conjunto de n elementos (es decir que, dado un conjunto de n niñas rubias, si una tiene los ojos azules, entonces todas tienen los ojos azules), y consideremos un conjunto de n+1 niñas rubias {R1, R2, ..., Rn+1}. Si suponemos que una de ellas, digamos R1, tiene ojos azules, entonces todas las del conjunto {R1, R2, ..., Rn} tienen ojos azules (por la hipótesis de inducción). En particular, R2 tiene ojos azules de modo que todas las del conjunto {R2, R3, ..., Rn+1} tienen ojos azules. En definitiva, todas las del conjunto {R1, R2, ..., Rn+1} tienen ojos azules.

A pesar de que la demostración parece correcta, entendemos que no lo es porque la afirmación es falsa. ¿Qué ha fallado? Simplemente, la suposición de que los conjuntos {R1, R2, ..., Rn} y {R2, R3, ..., Rn+1} tienen un elemento común es falsa cuando n = 1.

Hasta aquí la clase de matemáticas. Pasamos al juego de magia, cuya explicación esperamos que descubras, quizá ayudándote del principio de inducción. Realizaremos el juego de este mes con las mismas monedas que usamos la última vez, de momento una cantidad indefinida de ellas.

  1. Saca del bolsillo un puñado de monedas y colócalas en un montón sobre la mesa. Muestra también una predicción, que mantienes a la vista hasta el final pero sin dejar ver lo que contiene.

  2. Entrega un lápiz y una hoja de papel a una persona que quiera colaborar y, contigo de espaldas, pídele que realice las siguientes operaciones:

    • Separa las monedas en dos bloques, del tamaño que quieras, cuenta el número de monedas que tiene cada bloque y escribe el producto de sus dos valores.

    • Elige uno de los dos bloques anteriores -tú eliges-, vuelve a separarlo en otros dos bloques, vuelve a contar el número de monedas que tiene cada bloque, vuelve a multiplicar sus valores y escribe el producto.

    • Repite el mismo proceso del paso anterior: elige uno de los tres bloques, sepáralo en otros dos, cuenta el número de monedas que tiene cada uno y escribe el producto de estos dos valores.

    • Vuelve a repetir este proceso hasta que todos los bloques tengan una sola moneda. Al final, suma todos los números que habías anotado.

  3. Haz que comprueben que este valor coincide con tu predicción a pesar de la total libertad de elección de los distintos tamaños de los bloques de monedas en cada paso.

Veamos un ejemplo para comprender mejor el proceso:

  • Sobre la mesa hay diez monedas. Tu colaboradora la separa en dos grupos de 4 y 6 monedas. Por tanto, escribe el número 24.

  • A continuación, escoge el montón de 4 monedas y lo separa en dos grupos de 3 y una moneda. Escribe el número 3 debajo del 24.

  • Sobre la mesa hay tres montones, de 6, 3 y 1 moneda. Escoge el montón de 6 monedas y lo separa en dos grupos, de 4 y dos monedas. Escribe el número 8 debajo de los dos anteriores.

  • Luego escoge el montón de 4 monedas y lo separa en dos grupos, de 2 y 2 monedas. Escribe el número 4.

  • De momento, hay 5 montones, uno con tres monedas, tres con dos monedas y uno con una moneda. Escoge uno de los montones de dos monedas y lo separa en dos grupos de 1 moneda cada uno. Escribe por tanto el número 1.

  • Realiza dos veces más esta misma elección: divide el montón de dos monedas en dos grupos de una moneda y escribe el número 1.

  • Como quedan siete montones con una moneda y un montón con tres monedas, divide este en dos grupos de dos y una moneda y escribe el número 2. Por último, el montón que tiene dos monedas se divide en dos grupos y escribe el número 1.

Un esquema con el resumen de todo el proceso se muestra a continuación:









4
6









4 x 6 = 24







3
1
6








3 x 1 = 3






3
1
4
2







4 x 2 = 8





3
1
2
2
2






2 x 2 = 4




3
1
2
2
1
1





1 x 1 = 1



3
1
1
1
2
1
1




1 x 1 = 1


3
1
1
1
1
1
1
1



1 x 1 = 1

2
1
1
1
1
1
1
1
1


2 x 1 = 2
1
1
1
1
1
1
1
1
1
1

1 x 1 = 1

La suma de las cantidades anotadas es 24 + 3 + 8 + 4 + 1 + 1 + 1 + 2 + 1 = 45.

Las preguntas que debes plantear para saber de antemano el resultado final son: ¿este resultado depende del número inicial de monedas?, ¿depende también de la forma en que se separa cada montón en dos grupos?

Incluso aunque hayas intuido que las respuestas son sí y no, respectivamente, la pregunta final es: ¿cuál es la fórmula con la que se obtiene por adelantado el resultado final de la operación? Pero, más importante aún: ¿cómo demostrar que esa fórmula es la correcta?

Observaciones finales:

  1. Si no has logrado dar con la solución, puedes acudir a la fuente donde he encontrado este juego, el artículo de Franka Brückler titulado "Inductive Magic", aparecido en el blog Mathematics-in-Europe del Comité de Divulgación de la European Mathematical Society.

  2. Ya que hemos comentado el efecto dominó, no está de más sugerir que la caída de las fichas está relacionada también con algunas propiedades físicas, como se explica en este artículo titulado "Domino effect - it's more than just a fall".

Esta dirección electrónica esta protegida contra spambots. Es necesario activar Javascript para visualizarla
(Universidad del País Vasco - Euskal Herriko Unibertsitatea)

 
Volver