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 ser $R_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^ | Publicado el 1 de Septiembre de 2008
Categorías: Curiosidades, Geometría | Imprime este post

27 comentarios

Pablo Reyes | 1 de Septiembre de 2008 | 10:54

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!
Pablo Reyes | 1 de Septiembre de 2008 | 10:58

Bueno, en el enlace a MENSA veo que viene de ${n \choose 4} + {n \choose 2}+1$ . Aún así, seguro que debe estar explicado por algún sitio.
vengoroso | 1 de Septiembre de 2008 | 12:28

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…
odin | 1 de Septiembre de 2008 | 13:25

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.
Omar-P | 1 de Septiembre de 2008 | 14:10

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,…
Omar-P | 1 de Septiembre de 2008 | 14:59

Circle Division by chords:

http://mathworld.wolfram.com/CircleDivisionbyChords.html
Omar-P | 1 de Septiembre de 2008 | 16:19

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.
Carlos | 1 de Septiembre de 2008 | 16:23

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
Carlos | 1 de Septiembre de 2008 | 16:25

a, ya vi el link que dejo Omar-P
vengoroso | 1 de Septiembre de 2008 | 17:16

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.
Asier | 1 de Septiembre de 2008 | 17:50

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.
^DiAmOnD^ | 1 de Septiembre de 2008 | 19:42

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).
Asier | 1 de Septiembre de 2008 | 21:05

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”).
Omar-P | 1 de Septiembre de 2008 | 21:31

La sucesión vista anteriormente también corresponde al número de regiones en un espacio cuatridimensional formado por n-1 hiperplanos.
Omar-P | 1 de Septiembre de 2008 | 21:43

La ley fuerte de los pequeños números (En este link también se trata el tema):
http://mathworld.wolfram.com/StrongLawofSmallNumbers.html
^DiAmOnD^ | 1 de Septiembre de 2008 | 21:52

Ups, cierto.

Lo pongo en el post.
M | 1 de Septiembre de 2008 | 23:37

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}$
M | 1 de Septiembre de 2008 | 23:43

En http://www.maths.lth.se/matematiklu/personal/apas/Moser.html se puede ver otra prueba alternativa.
vengoroso | 1 de Septiembre de 2008 | 23:59

^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
M | 2 de Septiembre de 2008 | 0:25

gracias por el link, vengoroso. Sólo he ojeado muy por encima, pero me parece que lo que deducen la sección 2, cuando estudian la concurrencia de 3 diagonales, es consecuencia inmediata del teorema de Ceva para cuerdas (y el teorema de los siete círculos).

http://mathworld.wolfram.com/SevenCirclesTheorem.html

http://www.mathpropress.com/stan/bibliography/sevenCircles.pdf
vengoroso | 2 de Septiembre de 2008 | 0:59

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.
J. H. S. | 2 de Septiembre de 2008 | 19:19

Dejo aquí una liga para todos aquellos interesados en profundizar en el estudio de la Ley Fuerte de los Números Pequeños:

http://ndikandi.utm.mx/~lm2002070425/Guy.pdf

Espero sea de su agrado.

Hasta pronto.
Trackback | 3 Sep, 2008

Gaussianos » Probar y descubrir
Omar-P | 16 de Septiembre de 2008 | 2:49

EXEMPLUM MEMORABILE INDUCTIONIS FALLACIS
Euler
fede | 25 de Septiembre de 2008 | 3:30

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.
daniel | 18 de Noviembre de 2008 | 1:01

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
Andres | 25 de Enero de 2009 | 0:35

Quisiera saber como usando el Triangulo de Pascal, podemos determinar las regiones formadas en el problema anterior…