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:

  1. ¿Cuántos enlaces habría que colocar para comunicar 10 edificios todos con todos?

  2. ¿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.

Preguntas
  1. ¿Cuántos enlaces habría que colocar para comunicar \(n\) edificios todos con todos?

  2. ¿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.

Seguramente recuerdas o has oído del juego que jugábamos de niños y que consiste en encontrar la figura "oculta" uniendo un conjunto de puntos. Usa el pulsador de la esquina superior derecha para avanzar (flecha azul) y retroceder (flecha roja) recordando este juego. Puedes desplazar los puntos libremente. Al terminar, pulsa el botón 'Continuar'.

Realicemos un pequeño ejercicio mental.

  1. Imagina que tienes 2 puntos, mismos que conectas con 1 enlace.

  2. 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.

  3. Al repetir la operación de inciso 2), obtendremos 4 puntos conectados con 3 enlaces.

  4. Al repetir por tercera vez la operación del inciso 2), obtendremos 5 puntos conectados con 4 enlaces.
Este proceso lo podremos repetir indefinidamente obteniendo siempre algún número de puntos \(n\) conectados por \(n-1\) enlaces.

Si procedemos con todo rigor matemático podremos observar dos partes muy importantes en el proceso que acabamos de llevar a cabo:

  1. La propiedad inicial (\(n\) puntos, \(n-1\) enlaces) se cumple en el inciso 1) (2 puntos, 1 enlace).
  2. 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.

Pregunta

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:

  1. La propiedad se cumple para el número inicial.

  2. 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.