Cuidado con la intuición cuando hablamos de inducción

Comencemos planteando uno de los típicos problemas que abundan por internet en el que nos dan una serie de números y nos piden averiguar el siguiente. Ahí va:

Calcular el término siguiente de la siguiente serie:

1,2,4,8,16 \ldots

En principio la respuesta parece evidente, ¿verdad? Pues cuidado.

Supongamos que tenemos una circunferencia y vamos escogiendo puntos de la misma trazando posteriormente todos los posibles segmentos que conectan un par de puntos de los elegidos (exigimos que en ningún caso tres de estos segmentos se corten en un mismo punto, gracias Asier) contando después en cuántas regiones queda dividido el círculo que determina la circunferencia. Si escogemos sólo 1 punto no se pueden trazar segmentos y por tanto tendremos una única región. Si hemos escogido 2 puntos se puede trazar sólo un segmento y por tanto nos quedarán dos regiones. Si tenemos 3 puntos podemos trazar 3 segmentos que dividen al círculo en 4 regiones. Y así sucesivamente.

En el siguiente gráfico se puede ver con más claridad:

Círculo dividido en regiones

Podemos ver en cuántas regiones queda dividido el círculo trazando los segmentos de la manera antes descrita: 2 regiones para dos puntos, 4 regiones para tres, 8 regiones para cuatro y 16 regiones para cincoo (el caso cero, un punto, cero segmento y por tanto una región, no está contemplado en el gráfico pero es evidente).

Volvamos a preguntar: ¿qué número es el siguiente de la serie? Es decir, ¿en cuántas regiones queda dividido un círculo cuando trazamos todos los segmentos posibles que unen pares de puntos entre seis escogidos en una circunferencia? ¿Y si tomamos siete puntos?

Pues el tema parece llevarnos a lo siguiente:

Si llamamos R_n al número de regiones obtenidas con n puntos parece serR_n=2^{n-1}:

1 punto \longrightarrow R_1=2^{1-1}=2^0=1 región
2 puntos \longrightarrow R_2=2^{2-1}=2^1=2 regiones
3 puntos \longrightarrow R_3=2^{3-1}=2^4=4 regiones
4 puntos \longrightarrow R_4=2^{4-1}=2^3=8 regiones
5 puntos \longrightarrow R_5=2^{5-1}=2^4=16 regiones

Con lo cual, para seis puntos tendríamos 32 regiones.

Pero la realidad es otra: con seis puntos obtenemos 31 regiones. La sucesión que nos da el número de regiones a partir del número de puntos no es 2^{n-1}, sino que es la siguiente:

R_n= \cfrac{n^4-6n^3+23n^2-18n}{24}+1

Si la usamos para calcular el número de regiones vemos que va coincidiendo con la serie…hasta que llegamos a seis puntos. Ahí da 31 cuando debería dar 32. Además, conforme aumentamos el número de puntos los valores de las dos sucesiones van distando cada vez más.

Os dejo una tabla con los resultados:

n R_n 2^{n-1}
1 1 1
2 2 2
3 4 4
4 8 8
5 16 16
6 31 32
7 57 64
8 99 128

¿Conclusión? Pues como reza el título del post: cuidado con la intuición cuando hablamos de inducción. Además, respecto a la intuición no es la primera vez que avisamos.

Fuente: MENSA, aunque la fórmula de R_n está mal en el enunciado del juego.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

29 Comentarios

  1. Vaya, que curioso, jeje. Alguien se anima a averiguar el porqué de la sucesión? Me imaginaba algo mas “visible”.

    Por cierto, el enlace al post anterior (“una creencia no es una demostración”) está mal. Lo has acabado con unas comillas.

    Un saludo!

    Publica una respuesta
  2. Asumiendo que los puntos están en posición genérica, el número de regiones se puede calcular de manera sencilla usando la fórmula de Euler y un poquito de combinatoria elemental. Si tenéis mucho interés os esbozo la demostración, estoy un poco perezoso esta tarde…

    Publica una respuesta
  3. En realidad, conocer el siguiente termino es imposible sin alguna pista como por ejemplo que se trata de la sucesión más sencilla.
    Existen infinitas funciones que pasan por los puntos (1,1), (2,2), (3,4), (4,8), (5,16). Sin más que introducir un nuevo punto que sea (6,x) podemos hacer que el siguiente número de la sucesión sea x y hayar la función que nos daría el termino general.

    Publica una respuesta
  4. Es cierto lo que dices, DiAmOnD y es lógico que así suceda, pues las sucesiones se van ramificando. Se conocen cientos de sucesiones distintas que empiezan con 1, 2, 4, 8, 16,…

    Publica una respuesta
  5. Cuando nos preguntan ¿Cual es el siguiente tèrmino? ahora sabemos que pueden ser más de uno, generalmente muchos o incluso infinitos. Pero si tenemos que dar una única respuesta entonces creo que unas opciones interesantes podrían ser el de encontrar y mostrar el término producido por la expresión matemática más sencilla o sinó por el enunciado más breve.

    Publica una respuesta
  6. jejeje saludos a todos, efectivamente vengoroso tiene una buena idea de la demostracion, sí tiene que ver con combinatoria, de hecho el problema lo planteo Leo Moser, y la solucion también la podemos asociar a sumar filas del triángulo de Pascal de una forma determinada…
    a ver quien escribe la demostración completa

    Publica una respuesta
  7. Venga, va. Consideremos los n puntos en posición genérica (donde por genéricos entendemos que no hay tres cuerdas que se corten en el mismo punto). El dibujo de la situación nos determina un grafo en el plano, para el que debe verificarse la fórmula de Euler
    V-A+R = 1
    donde *NO* estamos contando la región exterior al círculo (por eso hay un 1 en vez de un 2). De aquí despejamos y tenemos que el número de regiones internas es
    R = 1 + A - V
    Supongamos que al dibujar todas las cuerdas tenemos I puntos de intersección entre ellas, entonces el número de vértices es V = n + I (los n puntos que pintamos en la circunferencia más los que aparecen por las intersecciones). Para las aristas, cada intersección (que se produce siempre en el corte de dos aristas) añade dos aristas nuevas (descomponemos cada una de las aristas en dos segmentos), por lo que tenemos A = \binom{n}{2} + n + 2I , donde aparecen \binom{n}{2} aristas debidas a las cuerdas (cada pareja de puntos nos determina una única arista), a las que les añadimos las 2I que aparecen por las intersecciones, y las n aristas que se corresponden con los arcos de la circunferencia.
    Juntando todo tenemos que el número de regiones viene dado sólo por el número de interseciones:
    R = \binom{n}{2} + I + 1
    Para concluír, basta observar que el número de intersecciones es precisamente el número combinatorio \binom{n}{4} ¿Y esto por qué es así? pues porque cada grupo de 4 puntos nos da lugar a un cuadrilátero inscrito en la circunferencia, y para dicho cuadrilátero nos aparece exactamente una intersección: la qe se obtiene a partir de las dos diagonales (las otras eventuales intersecciones entre las cuerdas definidas por estos puntos se encontrarían fuera del círculo, por lo que no nos interesan). Sustituyendo en lo anterior obtenemos la fórmula final
    R = \binom{n}{4} + \binom{n}{2} + 1
    que desarrollada nos da la expresión del post.

    Publica una respuesta
  8. para 6 puntos se pueden obtener también 30 regiones en lugar de 31, basta con que el sexto punto lo coloquemos de manera que una de las nuevas líneas a dibujar pase por una de las intersecciones ya creadas.

    Por lo tanto la fórmula solamente es válida para n puntos cuando por cada intersección no pasan más líneas. Diréis que para puntos tomados aleatoriamente la probabilidad de que esto ocurra es cero, pero no es un hecho imposible, matemáticamente puede darse el caso.

    Publica una respuesta
  9. Muy buena demostración vengoroso.

    Asier, podemos arreglar el problema que comentas considerando polígonos regulares inscritos en la circunferencia en vez de puntos escogidos aleatoriamente, ¿no? (a partir de 3 puntos, claro).

    Publica una respuesta
  10. precisamente los polígonos regulares son propensos a este tipo de cruces, un polígono regular de 2·n lados por ejemplo tiene n cruces en el centro, por eso el hexágono, octógono, etc. no nos valen.

    Hay que exigir que tres líneas no se crucen en el mismo punto, como se comenta en el link que ha puesto Omar-P (“joined by chords with no three internally concurrent”).

    Publica una respuesta
  11. La sucesión vista anteriormente también corresponde al número de regiones en un espacio cuatridimensional formado por n-1 hiperplanos.

    Publica una respuesta
  12. Me ha gustado la demostración, sí señor. Y también muy curiosa la relación que dejó entrever Carlos en conexión con el triángulo combinatorio. Si truncamos el triángulo por la sexta diagonal (nos quedamos únicamente con las 5 primeras diagonales), se obtiene la sucesión sumando las filas; es decir,

    {n-1\choose 0}+ {n-1\choose 1}+{n-1\choose 2}+{n-1 \choose 3}+{n-1 \choose 4}=n+{n\choose 4}+{n-1 \choose 2}=1+{n\choose 4}+{n \choose 2}

    Publica una respuesta
  13. ^DiAmOnD^, gracias, pero tiene menos mérito del que parece 😉

    Respecto a lo que comentáis acerca de los puntos múltiples de intersección o el número de regiones cuando los puntos se disponen de manera regular, el problema tiene bastante enjundia. Gerrit Bol fue el primero en proponer una solución para dichos números en 1936, pero sus fórmulas resultaron ser incorrectas. Por lo que yo sé, el problema no se resolvió hasta 1997, en el artículo The number of intersection points made by the diagonals of a regular polygon de Bjorn Poonen y Michael Rubinstein, publicado en SIAM Journal on Discrete Mathematics 11 (1998), no. 1, 135-156.

    El artículo es relativamente elemental, no involucra nada más complicado que algunos trucos que usan raíces de la unidad, pero las cuentas son duras, así que no se lo recomiendo a nadie que no esté muy aburrido. La fórmula que sale es… bueno, mirad el artículo 😉

    Publica una respuesta
  14. Vaya, todo un fan de la geometría sintética, por lo que veo… 😀

    Curioso el artículo de los siete círculos, el teorema de Ceva estaba enterrado en alguna parte de mi cabeza, pero no conocía esa aplicación… gracias por el enlace.

    Respecto a lo que comentas, efectivamente la ecuación de la sección 2 es la condición de concurrencia de Ceva, expresada de modo un poco particular expresando los puntos del polígono como raíces de la unidad. Lo interesante viene después, que es la clasificación de todas las soluciones de esa ecuación, y el cómo ver que a partir de las concurrencias de 3 rectas se pueden contar las concurrencias de orden mayor. A mí lo que más me sorprendió fue que (salvo el centro del polígono) no puedan existir puntos donde concurran más de 7 rectas simultáneamente.

    Publica una respuesta
  15. En algún comentario anterior se menciona el teorema de Ceva.

    Ese teorema está demostrado, unos 600 años antes que Ceva, por el rey geómetra Yusuf Al Mutaman Ibn Hud (Almutamín) , rey de la taifa de Zaragoza (Y contratista del Cid en alguna ocasión).
    Ceva
    Almutamín

    La verdad es que me acabo de enterar de esto…no sabía que la Aljafería está relacionada con la geometría del triángulo.

    Publica una respuesta
  16. hola quisiera saber como se resuelve problemas sobre de cuants formas se puede leer una palabra con el triangulo de pascal pero no esta de la manera tradicional (un triangulo), sino como un rombo o cuando se repite una letra como la palabra C O R R O E en un triangulo si alguien me ayuda se lo agradeceria. Gracias

    Publica una respuesta
  17. Quisiera saber como usando el Triangulo de Pascal, podemos determinar las regiones formadas en el problema anterior…

    Publica una respuesta
  18. Un amigo mío me consultó una interesante proposición : Supongamos que :Sea p(n) una proposición verdadera para todo n perteneciente a todos los naturales, entonces p(n) admite una demostración por inducción.

    En el momento le dije que era verdad, pero luego de profundizar en la idea empecé a dudar.A ver si alguien puede decirme algo al respecto.

    Publica una respuesta
  19. Se me olvidaba:¿Es posible demostrar que algo no se puede demostrar?

    Publica una respuesta
  20. Hola a todos. Es la primera vez que escribo en Gaussianos, aunque lo llevo siguiendo desde que estaba en la web antigua desde hace bastante tiempo. Al hilo de este post, me ha venido a la cabeza un articulillo que preparé con el profesor Juan de Burgos de la ETSIA sobre un tema parecido. Os dejo aquí el enlace:

    http://www.mat.uab.cat/matmat/PDFv2014/v2014n01.pdf

    Saludos,
    Antonio R.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Gaussianos » Probar y descubrir - [...] 9 en Cuidado con la intuición cuando hablamos de inducción [...]

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

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