jueves, 30 de septiembre de 2010

Todos los caballos son del mismo color: inducción matemática

Uno de los métodos que tenemos los matemáticos para demostrar resultados es el método de inducción.

Éste método se basa en una propiedad de los números naturales que dice que éste conjunto es el más pequeño que cumple que y . A los conjuntos que cumplen esta propiedad se les llama conjuntos inductivos.

La moraleja de todo esto es que para probar que una cierta propiedad, que se aplica a algunos números naturales, es cierta para todos, basta con demostrar que el conjunto de números naturales que verifican dicha propiedad es inductivo, por lo que como es el menor conjunto inductivo, se deduce que todos los naturales cumplen la propiedad.

¿Y cómo se prueba que un conjunto es inductivo? muy fácil. Primero se comprueba la propiedad para el caso inicial , que normalmente suele ser de lo más sencillo; y después se comprueba que si la propiedad es cierta para un número , entonces también es cierta para el número , esto es lo que se conoce como la hipótesis de inducción.

En resumen, si nos imaginamos que estamos en una escalera infinita y que cada peldaño es un número natural, lo que hacemos es probar el caso inicia, es decir, que podemos plantarnos en el primer escalón quietos; y después, con la hipótesis de inducción, probamos que (y así se lo explico yo a mis alumnos) podemos subir un escalón estemos donde estemos.

Pero claro, no todo es tan fácil como parece y a veces, el no comprender bien en qué consiste el método nos puede llevar a desagradables sorpresas como la que se dice en el título de este artículo.

Vamos a demostrar , que todos los caballos son del mismo color. Y lo vamos a hacer por inducción sobre el número de caballos que podemos elegir.

Para ello, el caso inicial, es trivial, si elijo 1 caballo, es evidente que es del mismo color que sí mismo, por lo que aquí no hay nada más que probar. Estamos en el primer peldaño de nuestra escalera.

Pasemos a probar la hipótesis de inducción. Vamos a suponer que si tenemos un grupo de caballos, entonces todos son del mismo color; y vamos a demostrar que si seleccionamos caballos, también todos son del mismo color.
Vamos a qudarnos con nuestros caballos y los ponemos en fila india. Si nos olvidamos del último, tendremos caballos, por lo que la hipótesis de inducción me dice que esos caballos son todos del mismo color. Ahora volvemos a nuestros caballos y nos olvidamos del primero de ellos, de nuevo tenemos otros caballos, por lo que de nuevo son todos del mismo color. Por lo tanto, si los primeros caballos son del mismo color y los últimos también... por fuerza todos los caballos son del mismo color.

Hala, ahí queda eso. ¿Cómo? ¿que aquí falla algo? ¿que tú tienes 1 caballo negro y otro blanco? ¿y tú uno marrón? Anda! entonces no todos los caballos son del mismo color... Pero si lo acabamos de demostrar!!!!

Pues claro, aquí hay un error y vuestro trabajo es descubrirlo, que apra eso están los comentarios. Por cierto, en la referencia [1], podéis encontrarla solución... pero claro, eso no se vale.

Tito Eliatron Dixit


Referencias:
[1] Su, Francis E., et al. All Horses are the Same Color, Math Fun Facts.
[2] Imagen extraída de la Wikipedia, original de bianditz en Flickr.

17 comentarios:

  1. "de nuevo tenemos otros n caballos, por lo que de nuevo son todos del mismo color"

    La pifia está en confundir un cardinal con un número natural.

    Un cordial saludo.

    ResponderEliminar
  2. @Cesar, me parece que en este caso no habría problemas. El error es de otra índole.

    ResponderEliminar
  3. Lo mismo digo burradas (yo me manejo con la matemática aplicada, las demostraciones me quedan muy lejos) pero a ver si me explico. Cuando afirmo que el subconjunto N del conjunto N+1 quitando el último son del mismo color y que el subconjunto N' del N+1 quitando el primero también lo son, lo único que puedo afirmar realmente es que tengo dos conjuntos con el mismo cardinal (n) pero no existen premisas que me permitan afirmar que los elementos de N y N' tengan el mismo color. Siguiendo tu ejemplo, no sé si puedo subir el escalón.

    ResponderEliminar
  4. ¡Ja! Bonito ejemplo. Yo lo incluí este semestre (aunque con gatos) en el curso de álgebra superior.

    ResponderEliminar
  5. El conjunto "Caballos" no es inductivo, por lo que los cardinales de sus subconjuntos no deben confundirse con elementos de "Números naturales". [Para explicar mi primer comentario.]

    ResponderEliminar
  6. El error está en el caso inicial, hay veces que el caso n=1 no es suficiente. Por ejemplo aquí estamos hablado de una propiedad que requiere más de un caballo, por lo que nuestro primer escalón, sería el caso n=2

    ResponderEliminar
  7. Espero no decir una burrada, pero en el error también está el aprendizaje, así que no tengo nada que perder.

    Cuando obviamos el último caballo, ciertamente tenemos n caballos y por tanto deben ser del mismo color, pero cuando volvemos a integrarlo en el grupo para siguientemente excluir al primero, volvemos a tener un conjunto de n + 1 caballos sobre el cual no podemos decir nada.

    ResponderEliminar
  8. Esta es de las falacias buenas, con el mismo razonamiento se puede demostrar que todos los números son iguales o que solo existe una partícula en el universo :D

    César, el fallo no es ese. Quizá sea el que dice Luis, digo quizá porque no estoy seguro de a qué se refiere (pero creo intuirlo).

    El fallo está aquí (si quieres pensarlo por ti mismo no sigas leyendo):

    "Por lo tanto, si los n primeros caballos son del mismo color y los n últimos también... por fuerza todos los n+1 caballos son del mismo color."

    Y no digo exactamente el fallo por si alguien quiere seguir pensándolo.

    ResponderEliminar
  9. Visto el comentario de Pini que ha publicado mientras yo escribía, añado que en la parte de mi comentario donde digo que está el fallo, hasta llegar a los puntos suspensivos todavía no se ha cometido, es decir, el paso

    "los n primeros caballos son del mismo color y los n últimos también"

    es correcto.

    ResponderEliminar
  10. @Carlos: Si te das cuenta Luís y yo decimos lo mismo con n=1.

    ResponderEliminar
  11. El lunes les contaba este mismo "problema" a mis alumnos, que llevaban picados una semana con él...
    Yo el chiste siempre lo acabo diciendo "y yo al menos tengo un pura sangre negro y un bonito corcel blanco", jajaja.

    A mí este problema siempre me ha encantado, creo que es de mis favoritos!!!

    ResponderEliminar
  12. @César. Uhm, ahora que veo tu segundo comentario, me pasa como con el de Luis, quizá lo que dices ahí tiene sentido, pero no me queda claro del todo lo que quieres decir. Lo que pasa es que tus otros comentarios son los que no me cuadran para nada, te comento:

    "La pifia está en confundir un cardinal con un número natural."

    Ahí no está la pifia. Y por cierto, los números naturales se definen precisamente como los cardinales finitos.

    "El conjunto "Caballos" no es inductivo, por lo que los cardinales de sus subconjuntos no deben confundirse con elementos de "Números naturales". [Para explicar mi primer comentario.]"

    Por definición los números naturales son los cardinales finitos así que no puede haber confusión por ser iguales. En cualquier caso, al deducir que del conjunto de n+1 elementos se tiene que los subconjuntos de n elementos son del mismo color no hay ningún problema, es un razonamiento correcto. La pega está al volver al caso n+1.

    @Tito Eliatron. Creo que este párrafo es bastante confuso:

    "¿Y cómo se prueba que un conjunto es inductivo? muy fácil. Primero se comprueba la propiedad para el caso inicial n=1, que normalmente suele ser de lo más sencillo; y después se comprueba que si la propiedad es cierta para un número n, entonces también es cierta para el número n+1, esto es lo que se conoce como la hipótesis de inducción."

    Preguntas inicialmente que como se comprueba si un conjunto es inductivo pero lo que explicas es cómo se aplica inducción, que son cosas distintas. Por ejemplo los números reales son un conjunto inductivo y en ese párrafo no se explica nada para demostrar que R es inductivo.


    Saludos!

    ResponderEliminar
  13. Pensaba que había publicado un comentario, se ve que dio error.

    @César. Quizá digas lo mismo que Luis en tu segundo comentario, pero al igual que no estoy seguro del todo de lo que quiere decir Luis, con el tuyo me pasa lo mismo. Por otro lado, tus otros 2 comentarios no tienen mucho sentido, de hecho eso de no confundir cardinales con números naturales... en teoría de conjuntos los naturales se definen como los cardinales finitos, así que no hay confusión posible. Sobre el conjunto de caballos se puede aplicar inducción sin problemas.

    @Tito Eliatron. Creo que lo que pone en este párrafo es un poco confuso:

    "¿Y cómo se prueba que un conjunto es inductivo? muy fácil. Primero se comprueba la propiedad para..."

    Lo que explicas en el párrafo no es como probar que un conjunto es inductivo sino que explicas lo que es aplicar inducción. Por ejemplo los números reales son un conjunto inductivo pero para comprobarlo no se hace lo que explicas.


    Saludos!

    ResponderEliminar
  14. El fallo es que con dos caballos,no siempre se cumpliria que tengan el mismo color aunque si que coincidan consigo mismos cuando se excluye un miembro. Por si no me explico bien, si excluimos el primero y tenemos en cuenta el segundo caballo(digamos color "x") este coincidara consigo mismo en color, y luego excluimos el segundo y tenemos en cuenta el primero(supongamos color "y") este tambien la cumplira y coincidira en color consigo mismo, pero el conjunto de los dos caballos no sera del mismo color.

    ResponderEliminar
  15. @Anonimo Esa es la respuesta que yo me esperaba.

    Para mçi, el problema es que el paso de inducción sólo es válido para $n\ge3$.
    Para que se cumpla lo que afirma el paso de inducción, debe cumplirse que la intersección de los conjuntos {n primeros caballos} y {n últimos caballos} sea no vacía, para lo que es preciso que haya al menos 3 caballos.

    ResponderEliminar
  16. Buena falacia. El defecto -como acota bien Tito- es que el razonamiento inductivo que se usa para pasar de n a n+1 es claramente inválido cuando n=1. Y así, la inducción no puede arrancar.

    ResponderEliminar

Si no comentas, Gauss se comerá una integral.
Y, por favor, respeta a todos con tus opiniones.