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.
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.
12 comentarios
Generic Cialis -
cristina -
Anónimo -
Guti -
Crystal -
Eratóstenes -
Demostrar algo es como montar un puzzle: la satisfacción llega al terminar, pero la diversión está en el proceso.
Ricardo -
Como mínimo, reforzar discreta, combinatoria (esenciales), y una buena base de cálculo.
Carlos -
jose -
Carlos -
jose -
Rimblow -