Sumando conocimiento (ejemplo de demostración)

En el post anterior sostuve que hacer matemáticas o estudiar una ciencia formal puede ser bastante distinto de lo que pensaban, incluso interesante para muchos de los que creían odiar la matemática, por una fea experiencia en el colegio. Para intentar convencerlos, prometí mostrarles como se puede demostrar una nueva verdad (o probar que una afirmación era falsa), mediante el siguiente ejemplo.

"En todo grupo de personas, hay al menos 2 personas que tienen la misma cantidad de amigos dentro del grupo."

Lo primero que uno suele hacer ante una afirmación de la cual desconoce si es verdad o mentira, es pensar en varios ejemplos para ver si se cumple la premisa. En caso de que encuentre un caso en el que no, puede concluir que efectivamente es falsa la premisa. Por ejemplo, si un amigo me dice que todas sus medias son blancas y encuentro un par negro en su cajón, la afirmación de él hubiese sido falsa. Esto se llama encontrar un contra-ejemplo y es una forma de demostración lógicamente válida y utilizada frecuentemente para demostrar la falsedad de algo. El equivalente para nuestro ejemplo sería encontrar un grupo de personas con determinada cantidad y determinadas amistades entre si, tal que NO ocurra que al menos 2 tienen la misma cantidad de amigos.

La realidad es que la afirmación es cierta, por lo cual nunca vamos a poder encontrar un contrajemplo. Pero entonces, ¿como podemos demostrar que es cierta?

El método de demostración que vamos a utilizar aquí (no es el único método que existe) consiste en partir de que la premisa es falsa, hacer una serie de deducciones lógicas válidas y llegar a un absurdo o contradicción. Habiendo encontrado esto, podemos asegurar que enotnces de lo que partimos es falso, por ende la premisa original era verdadera. Este método se lo conoce como reducción al absurdo.

Comencemos con la demo entonces. Separo en pasos para que vayamos digiriendo de a poco el asunto. Advierto que puede marear si uno no tiene práctica, es perfectamente normal, así que tómense el tiempo que sea necesario para leer en detalle y convencerse de cada paso.

     1. Supongamos entonces que NO sucede que en todo grupo de personas hay al menos 2 personas que tienen la misma cantidad de amigos dentro de ese grupo. Esto implica que existe un grupo de personas G (le ponemos un nombre por comodidad) en el que NO hay 2 o más personas con la misma cantidad de amigos.

     2. Esto a su vez implica que en G todas las personas deben tener una cantidad distinta de amigos. ¿Por qué? Porque si hubiese algún par de personas con misma cantidad de amigos, sería cierto que hay 2 o más personas con igual cantidad de amigos y dijimos que no era así.

     3. Sea N la cantidad de personas que hay en G. Entonces la cantidad de amigos máxima que puede tener una persona es N - 1, ya que como mucho puede ser amigo de todos pero no de si mismo. También sabemos que la cantidad de amigos mínima de alguien es 0 (que no sea amigo de nadie), por lo cual podemos concluir que la cantidad de amistades de toda persona está entre 0 y N - 1. Por ejemplo si en G hay 4 personas, las amistades serán un numero entre 0 y 3.

     4. Como dijimos que todos en G deben tener una cantidad distinta de amigos y hay N personas, los numeros de amistades son todos los numeros entre 0 y N - 1, ya que entre 0 y N - 1 hay exactamente N números distintos. Siguiendo el ejemplo de antes, si teniamos 4 personas, uno debe tener 0 amigos, otro 1 amigo, otro 2 y el cuarto debe tener 3 amigos.

     5. Pero si hay una persona en G con 0 amigos y otra con N - 1, significa que hay uno que no es amigo de nadie y otro que es amigos de todos. Absurdo! Si uno era amigo de todos también era amigo de ese que no tenía amigos.. pero entonces SI tenía amigos.

Podemos concluir entonces que NO existe un grupo en el que todas las personas tengan distinta cantidad de amigos. Entonces, queda demostrado que en todo grupo de personas hay al menos 2 personas con la misma cantidad de amigos.

A partir de esto, podemos afirmar entonces que ahora conocemos otra verdad del mundo. Si bien es cierto que no es una verdad demasiado interesante por si misma, la idea es mostrar como la ciencia, particularmente la lógica, junto con nuestra cabeza nos pueden revelar nuevas cosas. Y que hacer matemática puede ser muy distinto de lo que suponían.

Para terminar, de yapa les cuento que el ejemplo es el ejercicio 5.4 de las prácticas de la materia Algoritmos y Estructura de Datos III de la carrera de Ciencias de la Computación (Exactas - UBA).