Semáforos en rojo, leyes de Murphy y matemáticas: Demostraciones por inducción

Semáforos en rojo, leyes de Murphy y matemáticas: Demostraciones por inducción

Hoy vamos a conducir por ciudad. Subimos al coche y enseguida nos encontramos el primer semáforo. Está en rojo. Poco después llegamos al segundo semáforo. También está en rojo. Seguimos conduciendo y llegamos al tercer semáforo. ¡Maldición! Otro más en rojo.

¿Significa eso que todos los semáforos que te encuentres estarán en rojo?

Por suerte no (aunque habrá días peores que otros) 😉 Sería verdad si se cumpliera esta ley de Murphy:

 Si te encuentras con un semáforo en rojo, el siguiente también estará en rojo.

En ese caso, como el primero estaba en rojo, el segundo también lo estaría. Como el segundo lo estaba, el tercero también lo estaría y así, uno detrás de otro, nos encontraríamos todos los semáforos en rojo…

Semáforos en rojo

Ahora vienen las matemáticas, pero que nadie se asuste, que hoy sólo vamos a usar números naturales.

Primer ejemplo:

  • Empezamos por el número (1), para el que se cumple que (1^2<1cdot 10) (un semáforo en rojo).
  • Después llegamos al número (2) y vemos que también cumple que (2^2<2cdot 10) (dos semáforos en rojo).
  • Seguimos con el (3) y resulta que también (3^2<3cdot 10) (tres semáforos en rojo).

¿Significa eso que para cualquier número natural (n) se va a cumplir que (n^2<ncdot 10) (que todos los semáforos van a estar en rojo)?

Pues no, porque para (10) tenemos que (10^2) no es menor que (10cdot 10) (después de (9) semáforos, el siguiente ya no está en rojo).

Lo que pasa aquí (igual que con los semáforos) es que no es cierta la correspondiente ley de Murphy, que en este caso diría

Si para un número (k) se cumple que (k^2<kcdot 10) (un semáforo estaba en rojo) entonces para el siguiente número, (k+1), también se cumple que ((k+1)^2<(k+1)cdot 10) (el siguiente semáforo también estará en rojo).

y que, como hemos visto, falla para (k=9).

Segundo ejemplo:

  • Empezamos por el número (1), para el que se cumple que (4^1 -1) es múltiplo de (3) (un semáforo en rojo).
  • Después llegamos al número (2) y vemos que también cumple que (4^2 -1) es múltiplo de (3) (dos semáforos en rojo).
  • Seguimos con el (3) y resulta que también (4^3 -1) es múltiplo de (3) (tres semáforos en rojo).

¿Significa eso que para cualquier número natural (n) se va a cumplir que (4^n -1) es divisible por (3) (que todos los semáforos van a estar en rojo)?

Puedes probar con unos cuantos números más y comprobarás que para todos se cumple… pero eso no garantiza nada porque ¿quién te dice que no falla justo alguno de los que no has comprobado?

Así que hemos llegado a un punto en el que estamos más o menos convencidos de que la propiedad es cierta, pero no podemos probar con toooodos los números (porque hay infinitos). Entonces es momento de preguntarse si se cumple la correspondiente ley de Murphy, que en este caso diría

Si para un número (k) se cumple que (4^k -1) es divisible por (3) (un semáforo estaba en rojo) entonces para el siguiente número, (k+1), también se cumple que (4^{k+1} -1) es divisible por (3) (el siguiente semáforo también estará en rojo).

Como hemos visto que el primer semáforo estaba en rojo, si además se cumple esta ley de Murphy entonces podremos estar seguros de que todos los semáforos estarán en rojo. Es decir, que la propiedad se cumplirá para cualquier número natural.

Cascada de fichas de dominó

Pues venga, vamos a ver entonces que esta ley de Murphy sí se cumple.

Queremos ver que (4^{k+1} -1) es divisible por (3)  sabiendo que (4^k -1) es divisible por (3):

  • Para ello el truco es escribir (4^{k+1}-1) de manera que aparezca (4^k -1), que es para el que sabemos algo, así que podemos ponerlo como:

(4^{k+1}-1= 4cdot 4^k -1 =4cdot 4^k -4 +3 = 4cdot (4^k -1) +3).

  • Ahora vamos a ver que los dos sumandos de la derecha son divisibles por (3):
    • Por un lado, sabemos que (4^k -1) es divisible por (3) (el semáforo que ya estaba en rojo), así que el primer sumando es divisible por (3).
    • Por otro lado, el segundo sumando también es divisible por (3) porque de hecho es igual a (3).
  • Entonces la suma de la derecha, que era igual al (4^{k+1}-1) que teníamos a la izquierda (el siguiente semáforo), es suma de dos cosas divisibles por (3), así que también es divisible por (3) (el siguiente semáforo también estará en rojo). Y esto era lo que queríamos ver.

Así que puedes probar con todos los números naturales (n) que quieras y no encontrarás ninguno para el que no se cumpla que (4^n -1) sea divisible por (3), te lo garantizan las matemáticas. 🙂

 

Para saber más:

En matemáticas esta técnica se llama inducción (sí, como la de las cocinas) y es una de las técnicas que se usan para poder garantizar que una propiedad se cumple. Es decir, para demostrar esa propiedad.

Algunas de las propiedades que pueden demostrarse usando inducción son, por ejemplo:

  • Que la suma de los números desde (1) hasta (n) es (frac{ncdot(n+1)}{2}).
  • Que la suma de los ángulos interiores de un polígono convexo de (n) lados es ( (n-2)cdot 180) grados.

Pero aquí tienes muchas más. Si te animas a hacer tu propia demostración usando inducción, cuéntanoslo en los comentarios.

También puede usarse inducción para determinar el número de movimientos necesarios para resolver el rompecabezas de las torres de Hanoi.

Por último, es interesante saber que hay una variante de la inducción llamada inducción fuerte, con la que se pueden demostrar otro tipo de propiedades. Por ejemplo, que cualquier número natural puede descomponerse como producto de números primos (pero eso lo dejaremos para otro día).

 

Imágenes: Sarah Jane en Flickr y aussiegall en Wikimedia Commons.

 

Nota 1: Permitidme dedicar esta entrada a la memoria de mi compañero de departamento y comidas, José Antonio Malpica Velasco, al que ayer se le apagaron los semáforos.

Nota 2: Esta entrada  se pudo votar en Menéame.

Puedes seguirnos en Twitter, Facebook y Google +.



12 respuestas a «Semáforos en rojo, leyes de Murphy y matemáticas: Demostraciones por inducción»

  1. Avatar de Slayer
    Slayer

    Siempre recordare un profesor de Algebra que demostro que si en clase habia una rubia con ojos azules, todos eramos rubias con ojos azules.

    1. Avatar de David Orden

      Slayer: Un clásico, como muestra Eliatrón.

      Chandler: Por pedir que no quede.

      tenanes: los recuerdos de primero de carrera perduran casi más que los del último año.

      Freud: intentaré escribir algo Simpson, me pongo a pensar en ello.

      Gracias a todos.

  2. Avatar de Celedonio
    Celedonio

    @ Pagaría por verle Slayer de rubia con ojos azules…

  3. Avatar de Cornelius
    Cornelius

    Una forma interesante de resolver que 4^(k+1)-1 es múltiplo de 3 es factorizándolo:

    (4^(k+1)-1)=(4-1)*(4^k+4^(k-1)+…+4+1)

    Y tenemos un factor que es (4-1)=3

    1. Avatar de David Orden

      Chsss, no se lo digas a nadie 😉 De hecho, de cualquiera de las dos maneras se demuestra fácilmente algo más; que (x^n-1) es múltiplo de (x-1).

  4. Avatar de Tito Eliatron

    Con inducción (y un poquitín de trampa) se puede demostrar que Todos los hombres somos iguales.
    Supongo que será algo parecido a lo que decía el primer comentarista.

  5. Avatar de Chandler
    Chandler

    Matemáticas y coches juntos. ¿Se puede pedir algo más?

  6. Avatar de tenanes
    tenanes

    Demostraciones por inducción…
    que recuerdos del primer año de carrera.

  7. Avatar de Freud
    Freud

    Por inducción también: si pones a «n» gatos en un recipiente u olla de tamaño considerable* (a eso de las 3:00 de la madrugada) y pones la placa de inducción al máximo, en menos que canta un gallo todos los gatos se volverán pardos, con lo que se demuestra que de noche todos los gatos son pardos.

    *Este experimento se ha realizado a través de una simulación por ordenador. Ningún animal, a excepción del investigador humano, ha sufrido daños durante la realización de este experimento. Este experimento ha sido patrocinado por «Itchy and Scratchy». They fight, and bite. They fight and bite and fight. Fight fight fight, bite bite bite. The Itchy and Scratchy Show!

  8. Avatar de kiddo
    kiddo

    Lo siento pero no entiendo que tiene que ver lo de los semaforos con la formula k2<k⋅10
    Slayer, no te acordaras de la demostracion?

    1. Avatar de David Orden

      kiddo: La fórmula correspondería al semáforo. El que la fórmula se cumpla correspondería a que el semáforo esté en rojo.

      1. Avatar de David Orden

        En Menéame acaban de hacer un comentario muy interesante, relacionando esta entrada con la «ola verde» de semáforos.

        Por cierto; aún se puede menear la entrada, si no lo habéis hecho ya 😉

Responder a Celedonio Cancelar la respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Sobre el autor
Fotografía del autor

Soy profesor del área de Matemática Aplicada en la Universidad de Alcalá. Me interesa aprender y ayudar a aprender. Me gusta conectar las matemáticas con otros campos. Cuento cosas en Twitter como @ordend. Tengo una página profesional con más información.

Sobre el blog

Este blog trata sobre matemáticas, miradas desde distintos puntos de vista. Pretende ser cooperativo, porque seguro que hay algo de lo que sabes más que otros y, aunque no lo hayas pensado nunca, tiene matemáticas detrás. Queremos pasarlo bien jugando a pensar y ayudarnos entre todos a aprender cosas. Puedes seguir a @cifrasyteclas en Twitter o visitarnos en Facebook.

Entradas recientes
Comentarios recientes
  1. Hola, cualquier número (que no sea 0) elevado a la 0 da 1. Saludos

  2. Muy interesantes explicaciones, tanto para 0! como para nº(exponente 0). El tema se me ha actualizado a razón de algunas…

FIltro
Nube de etiquetas

Acertijo Alumnos Carnaval de Matemáticas Charla Ciencia Circunferencia Coches Concurso Conducir Cruces decimal Divulgación Erdős Estudiantes Gala Geometría Computacional Grafo Gráfica Guadalajara Imagen Ingeniería Investigación Juego Madrid Malla Matemáticas Motor Naturales Número Números Pi Plano Premios Primos Probabilidad Problema Problemas abiertos Puntos Segmentos Suma Teoría de números Triángulo Universidad Universidad de Alcalá Utiliza matemáticas