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

Matemática: Derribando mitos (y despertando curiosos)

"Educación es lo que a uno le queda después de olvidar todo lo que aprendió en la escuela." - Albert Einstein.

          Entrar a la facultad de Exactas y ver lo desierta que está comparado a cuando uno se acerca a una sede de Sociales (o de cualquier otra facultad) despierta muchas preguntas. Y enseguida uno piensa en la experiencia previa de la gran mayoría de la gente que entra a la facultad: la escuela. Se acuerda de lo que era matemática en el colegio (en realidad del colegio en general! :| pero eso dejémoslo para otro post) y ahí uno empieza a entender. A poca gente le puede interesar aprender/memorizar una serie de reglas mecánicas que no les encuentra sentido. A uno lo obligaban a aprender algo aparentemente inútil sin dar un buen motivo. Peor aún, desde chico nos hacían hacer cuentas, ¿por qué hacer cuentas molestas cuando tenemos la calculadora a mano? Es como que enseñarnos a escribir con tinta china! Hace 5 años que estudio una ciencia formal, estoy rodeado de matemática, pero creo que si me preguntás como dividir dos numeros grandes en una hoja me metés en un apuro, que me intimide al menos por unos minutos... me olvidé!

          Pero por haber estudiado algo de matemática luego (sic) probablemente pueda deducir el método. Y ahí está clave de todo. Deducir. Razonar. No tiene sentido recordar reglas o fórmulas que uno puede encontrar en Wikipedia en 30 segundos. Tampoco perder el tiempo haciendo procedimientos molestos que una computadora puede hacer mucho más rápido que nosotros. Lamentablemente el colegio, al menos las clases de matemática pre-secundario, nos transmitieron que hacer matemática era hacer cuentas. ¿Quien no tiene (o tuvo) la imagen infantil de que un genio matemático es quien puede resolver rápidamente cuentas con números muy grandes? Nada más lejos de la realidad.

          Por suerte las cuentas disminuyeron cuando nos acercábamos a los 18, pero la obligación a entender conceptos sin encontrar un motivo o una utilidad nos siguió acompañando hasta salir del secundario. De hecho, salvo que hayan tenido la suerte de estudiar esto seriamente luego (o de haber escuchando atentamente a Adrián Paenza algún día), probablemente sigan reteniendo esa misma falsa imagen. El problema principal de esto NO es que aleje a la gente de estudiar matemática (ya que de hecho estudiarla como carrera probablemente sea interés de una minoría) sino pensar que hacer matemática en todas sus formas o, peor aún, estudiar algo relacionado con esto, es tan desagradable y poco atractivo como hacer cuentitas o memorizar y aplicar reglas.

          Lo más interesante de todas las ciencias formales, a mi entender, es aprender a razonar y darse cuenta del poder que tiene la mente. Como uno puede construir nuevas verdades para nada obvias y desconocidas hasta el momento, partiendo de algunos conocimientos con sólo razonar y nada más, es realmente sorprendente. No exagero al decir que te abre la cabeza y te hace ver el mundo de nuevas maneras. Y para construir esa nueva verdad, un paso fundamental es poder demostrar su veracidad. Por esto, aprender a demostrar algo, pudiendo afirmar a ciencia cierta que esto es así, que es tan irrefutable como que 1 + 1 es 2, es algo poderoso y que llama la atención si se detienen a pensarlo. Es una manera en que el hombre puede progresar. Pero no pretendo que me crean lo que digo, sino traten de verlo por ustedes mismos con un simple ejemplo. O aunque sea hacer el esfuerzo y quedarse con la idea que la matemática es otra cosa y hasta quizás se den cuenta que puede ser interesante para muchos, o incluso para ustedes, quien sabe.

          Supongan que yo les digo lo siguiente: En todo grupo de personas, hay al menos 2 personas que tienen la misma cantidad de amigos dentro del grupo. O sea yo les afirmo que si le preguntan a un grupo de gente que conozcan quien es amigo de quien, van a ver que siempre al menos 2 personas (quizás más) tienen exactamente la misma cantidad de amigos cada uno. Por ejemplo, si pensamos en un grupo de 2 personas, tenemos 2 situaciones, que sean amigos o que no. En ambos casos, los dos tiene la misma cantidad de amigos: o un amigo o ninguno. ¿Se entiende? Piénsenlo un rato si se marearon.

          Para un grupo de 2 personas parece ser cierto, pero... ¿Es cierto que esto se cumple para un grupo con más personas? Si es así, ¿como podríamos demostrar a ciencia cierta que efectivamente es cierto, sin importar cuanta gente haya en el grupo? Y si es falso, ¿como demostraríamos que es mentira? Yo por el momento paro acá porque esto se está haciendo largo, pero si llegaste hasta acá, te invito a leer en estos días las respuestas a estas preguntas,  y algunas cosas más.

SEGUNDA PARTE