Formalización del problema
Objetivo
Aunque ya lo hemos mencionado someramente, algo que vamos a lograr en esta unidad es resolver el problema que nos hemos planteado de una forma general, es decir, desarrollaremos un procedimiento para optimizar una red de \(n\) puntos, con \(n\) un número natural arbitrario, \(n\ge2\), y considerando que tenemos un cuadro de costos para la conexión de cada par de estos \(n\) puntos.
Parámetros útiles
En la primera página del planteamiento del problema nos preguntamos dos cosas:
- ¿Cuántos enlaces habría que colocar para comunicar 10 edificios todos con todos?
- ¿Cuál es el número mínimo de enlaces que requerimos para conectar los 8 edificios? ¿Y si fuera un número más grande, digamos cien o mil?
Como buscamos un procedimiento general para un número de enlaces \(n\ge2\) arbitrario, es conveniente responder las dos preguntas anteriores en este tenor, transformándolas en las que se presentan a continuación.
- ¿Cuántos enlaces habría que colocar para comunicar \(n\) edificios todos con todos?
- ¿Cuál es el número mínimo de enlaces que requerimos para conectar los \(n\) edificios?
Las respuestas a estas preguntas nos brindarán dos datos muy útiles para la formalización que estamos llevando a cabo. Sabremos cuántos enlaces requerimos para la solución óptima y de qué tamaño es el cuadro de enlaces, es decir, cuántos datos debemos tener.
Principio de inducción matemática
Estamos seguros de que conoces, o estás sumamente cerca de, la respuesta a la segunda pregunta.
Realicemos un pequeño ejercicio mental.
- Imagina que tienes 2 puntos, mismos que conectas con 1 enlace.
- Si en la imagen mental que tenemos aparece otro punto, entonces basta con poner 1 enlace con alguno de los puntos que ya teníamos conectados entre sí. Tendremos 3 puntos conectados con 2 enlaces.
- Al repetir la operación de inciso 2), obtendremos 4 puntos conectados con 3 enlaces.
- Al repetir por tercera vez la operación del inciso 2), obtendremos 5 puntos conectados con 4 enlaces.
Si procedemos con todo rigor matemático podremos observar dos partes muy importantes en el proceso que acabamos de llevar a cabo:
- La propiedad inicial (\(n\) puntos, \(n-1\) enlaces) se cumple en el inciso 1) (2 puntos, 1 enlace).
- Al incrementar la \(n\) cuando realizamos la operación del inciso 2), la propiedad siempre se mantiene.
Los dos incisos anteriores son los componentes que permiten aplicar el principio de inducción matemática y así garantizar que la propiedad se cumple para cualquier número natural \(n\ge2\).
Sí, la inducción matemática no solo parece un
concepto sumamente sencillo, ¡lo es!
De hecho, la gran
diferencia entre su simplicidad y su potencia es lo que a veces
puede llegar a confundirnos.
El mismo compañero al que le pareció extraño el cuadro de costos de los enlaces ahora nos hace una observación interesante. Dice que la propiedad (\(n\) puntos, \(n-1\) enlaces) también se cumple cuando \(n=1\). ¿Qué opinas?
De ser cierto lo anterior, aunque no nos es muy útil en la práctica armar redes de un solo punto, podremos afirmar que la propiedad se cumple para cualquier número natural \(n\ge1\).
En resumen
El principio de inducción matemática consiste en establecer, sin lugar a dudas, que una propiedad se cumple para cualquier número natural que sea mayor que o igual a un número natural inicial. Esto se consigue garantizando que:
- La propiedad se cumple para el número inicial.
- Suponiendo, o dando por hecho, que la propiedad se cumple para un número natural arbitrario \(n\), podemos garantizar que se cumplirá para \(n+1\).
Avanza a la siguiente página donde comenzaremos aplicando la inducción al primer parámetro.