Blogia
Tio Petros

El principio de correspondencia.

Nunca con tan humilde herramienta se consiguió tanto.

Uno de los atributos que puede tener una demostración matemática es la elegancia. Este atributo forma parte de ese conglomerado de cualidades que reunimos bajo el nombre de belleza, y que aunque no sabemos definir, percibimos perfectamente.

La elegancia de una demostración es una de las cualidades más objetivas dentro de todas ellas, y tiene mucho que ver con la longitud de la demostración: cuanto más concisa sea, será más elegante. Desde luego, una demostración bien hecha es incontrovertible, y expresa una verdad inmutable dentro de su campo de definición; pero hay demostraciones bellísimas, y otras que no lo son. Cuando vemos la matemática no sólo como una herramienta para comprender el mundo, ni siquiera como una forma de acceder a ciertas verdades, sino como una aspiración estética, no nos conformamos con saber un hecho, sino con el placer que nos produce su conocimiento, y sobre todo el camino recorrido para acceder al mismo.

Lo mismo sucede con un ajedrecista que no se conforma con ganar una partida (supuesto fin del juego, no lo olvidemos). Juega porque ama el juego, y sabe que hay partidas ganadas que son chapuceras; y partidas bellas incluso entre las perdidas.

El Principio de correspondencia es una humildísima herramienta que puede ser utilizada de forma celestial produciendo enorme elegancia en muchas demostraciones combinatorias.

Es algo tan tonto como esto:

Dos conjuntos finitos cuyos elementos pueden ponerse en correspondencia uno-uno, son del mismo tamaño.

Cuando tenemos que calcular el tamaño de un conjunto, podemos encontrar otro de su mismo tamaño más fácil de medir. Ese es todo el misterio. Lo bueno es que los problemas se pueden simplificar sorprendentemente si elegimos un buen conjunto auxiliar.

Pongamos un par de ejemplos.


En una liga de n equipos de fútbol se deben jugar partidos eliminatorios hasta que quede uno solo, que será el campeón. Cada partido acaba con la victoria de un equipo, pues se llega si es necesario a los penaltis. Si en un momento el número de equipos es impar, se queda uno al azar sin jugar esta etapa, pasando automáticamente a la siguiente. ¿Cuántos partidos se deberán jugar en toda la liga?

1.- RESOLUCIÓN POR CONTEO DIRECTO.

Si el número de equipos fuera potencia de 2, pongamos 2k, el cálculo sería muy sencillo. En primera fase se eliminarían n/2=2k-1, la segunda n/4=2k-2, las sucesivas n/8, n/16... hasta llegar a la final en la que habrá 2 equipos a jugar, y se eliminaría uno. La suma será 2k-1+2k-2+...+1=2k-1= n-1.

Cuando el número de equipos inicial no sea potencia de dos, la cosa se complica: unas veces será par el número de equipos, y otras será impar, con lo que el tratamiento deberá ser diferente. No se trata de un problema insalvable, pero complica extraordinariamente el cálculo. Al final llegaríamos al resultado de que se jugarán siempre (n-1) partidos.

2.- RESOLUCIÓN MEDIANTE EL PRINCIPIO DE CORRESPONDENCIA.

Cada partido supone la eliminación de un equipo. Cada equipo eliminado lo ha sido en un partido. Luego el número de partidos será igual al número de equipos a eliminar: (n-1).

En un renglón hemos demostrado con total generalidad el problema, sea cual sea el número inicial de equipos. Esta es más elegante que la anterior, ¿verdad?

Otro ejemplo:

¿Cuántos subconjuntos tiene un conjunto de n elementos?

1.- RESOLUCIÓN POR CONTEO DIRECTO

Contaremos los subconjuntos existentes para cada tamaño de los posibles. De tamaño cero habrá un subconjunto: el vacío. De tamaño 1 habrán n subconjuntos. En general, de tamaño k, con k menor o igual que n habrá un número de subconjuntos igual a las combinaciones de n tomados de k en k. Extendiendo dicha suma desde cero hasta n comprobaremos que la expresión resultante es 2n.

2.- RESOLUCIÓN MEDIANTE EL PRINCIPIO DE CORRESPONDENCIA.

Para cada subconjunto, un elemento del conjunto inicial tiene dos posibilidades: pertenecer o no al subconjunto. El número de subconjuntos será igual al tamaño del conjunto de posibilidades cruzadas de los n elementos, que es obviamente 2n.

Ya me dirán ustedes si no es enorme la utilidad de una herramienta tan simple. Lo que no es simple, es encontrar el conjunto útil para el conteo; ahí reside la inteligencia de la demostración, y a veces incluso la genialidad.
¿Y esta publicidad? Puedes eliminarla si quieres
¿Y esta publicidad? Puedes eliminarla si quieres

12 comentarios

Generic Cialis -

Hola, yo tengo que hacer un trabajo sobre el principio de correspondecia y esta informacion me sirvio para complementar muchas cosas de mi projecto.

cristina -

yo quiero que me den pautas para trabajar la correspondencia en niños de edad de tres y cuatro años

Anónimo -

Guti -

Yo que quieres q te diga... he empezado la licenciatura de matematicas hace una semana, y para demostrar el numero de subcojuntos posibles en un conjunto nos tiramos una hora y media...

Crystal -

Elegante post y elegante comentario sobre los puzzles: ¿alguien se ofrece a rizar el rizo?

Eratóstenes -

Elegante el principio y elegante la exposición. Como siempre.

Demostrar algo es como montar un puzzle: la satisfacción llega al terminar, pero la diversión está en el proceso.

Ricardo -

De todas maneras, y teniendo en cuenta que en su día todos los buenos informáticos fueron matemáticos, creo que los informáticos deberíamos formarnos un poco más en matemáticas, dado que nuestra actual titulación como ingeniería lo descuida un poco.

Como mínimo, reforzar discreta, combinatoria (esenciales), y una buena base de cálculo.

Carlos -

Por supuesto que se puede.La licenciatura en matemáticas es mejor para aprender matemáticas que cualquier otra. ¿ Estaremos deacuerdo no? Informática será mejor que matemáticas en informática , física en física , etc

jose -

Bueno, bueno... Yo sólo hablaba de matemática discreta. Esta asignatura, en esta universidad, durante este año. Tampoco es bueno generalizar por las buenas a toda la carrera y decir que una licenciatura, en general, es mejor (distinta, pero vamos, se ve lo que se quería decir) que otras ¿no?

Carlos -

Pues mal hace tu profesor. A nosotros nos explicaron la combinatoria precisamente por medio de aplicaciones entre conjuntos y no mediante meras fórmulas para aprenderse y aplicar ... Por eso ponían énfasis en "aprender a contar", que es precisamente lo que tio Petros está señalando con este principio ... En estos detalles se diferencia la licenciatura en matemáticas a otras ingenierías,física ...

jose -

Pues a nosotros el profesor nos pone a calcular combinaciones como locos, a lo mejor espera que a un coco brillante se le ocurra solucionar los problemas de combinatoria mediante esta técnica... sin éxito, de momento. (y ya pasamos al tema siguiente, así que tendrá que esperar otro año.. en fin)

Rimblow -

Me encanta "el principio de correspondencia", y más me encanta como lo has desarrollado, y de que forma lo has descripto, estoy totalmente de acuerdo contigo, lo importante es el camino, no el princio ni el fin... (aún si estos te acompañan, pues mejor)
¿Y esta publicidad? Puedes eliminarla si quieres