Dividir un círculo en áreas - Dividing a circle into areas

El número de puntos ( n ), acordes ( c ) y regiones ( r _G ) para los primeros 6 términos del problema del círculo de Moser

En geometría , el problema de dividir un círculo en áreas por medio de un polígono inscrito con n lados de tal manera que se maximice el número de áreas creadas por los bordes y diagonales , a veces llamado problema del círculo de Moser , tiene una solución por un inductivo método. El mayor número posible de regiones, r _G = ( ⁿ
₄ ) + ( ⁿ
₂ ) + 1 , dando la secuencia 1, 2, 4, 8, 16, 31, 57, 99, 163 , 256, ... ( OEIS :  A000127 ). Aunque los primeros cinco términos coinciden con la progresión geométrica 2 ^{n - 1} , diverge en n = 6 , lo que muestra el riesgo de generalizar a partir de unas pocas observaciones.

Lema

Si hay n puntos en el círculo y se agrega un punto más, se pueden dibujar n líneas desde el nuevo punto a puntos previamente existentes. Son posibles dos casos. En el primer caso ( a ), la nueva línea pasa por un punto donde se cruzan dos o más líneas antiguas (entre puntos previamente existentes). En el segundo caso ( b ), la nueva línea cruza cada una de las antiguas en un punto diferente. Será útil conocer el siguiente hecho.

Lema . El nuevo punto A puede elegirse de modo que el caso b ocurra para cada una de las nuevas líneas.

Prueba . Para el caso a , tres puntos deben estar en una línea: el nuevo punto A , el antiguo punto O en el que se traza la línea y el punto I donde se cruzan dos de las viejas líneas. Hay n puntos antiguos O y, por tanto, un número finito de puntos I donde se cruzan dos de las líneas antiguas. Para cada O y I , la línea de OI cruza el círculo en un punto que no sea O . Dado que el círculo tiene infinitos puntos, tiene un punto A que no estará en ninguna de las líneas OI . Entonces, para este punto A y todos los puntos antiguos O , el caso b será verdadero.

Este lema significa que, si hay k líneas que cruzan AO , entonces cada una de ellas cruza AO en un punto diferente y k + 1 nuevas áreas son creadas por la línea AO .

Solución

Método inductivo

El lema establece una propiedad importante para resolver el problema. Empleando una prueba inductiva , se puede llegar a una fórmula para f ( n ) en términos de f ( n - 1).

En la figura, las líneas oscuras conectan los puntos 1 a 4 que dividen el círculo en 8 regiones en total (es decir, f (4) = 8). Esta figura ilustra el paso inductivo de n = 4 an = 5 con líneas discontinuas. Cuando se agrega el quinto punto (es decir, cuando se calcula f (5) usando f (4)), esto da como resultado que se agreguen cuatro nuevas líneas (las líneas discontinuas en el diagrama), numeradas del 1 al 4, una por cada punto que se conectar a. Por lo tanto, el número de regiones nuevas introducidas por el quinto punto puede determinarse considerando el número de regiones agregadas por cada una de las 4 líneas. Configure i para contar las líneas que se agregan. Cada nueva línea puede cruzar varias líneas existentes, según el punto al que se encuentre (el valor de i ). Las nuevas líneas nunca se cruzarán, excepto en el nuevo punto.

El número de líneas que intersecta cada nueva línea se puede determinar considerando el número de puntos a la "izquierda" de la línea y el número de puntos a la "derecha" de la línea. Dado que todos los puntos existentes ya tienen líneas entre ellos, el número de puntos de la izquierda multiplicado por el número de puntos de la derecha es el número de líneas que cruzarán la nueva línea. Para la recta al punto i , hay

n - yo - 1

puntos a la izquierda y

i - 1 puntos

a la derecha, por lo que un total de

( n - yo - 1) ( yo - 1)

deben cruzarse las líneas.

En este ejemplo, las líneas a i = 1 ei = 4 cruzan cada línea cero, mientras que las líneas a i = 2 e i = 3 cruzan cada una dos líneas (hay dos puntos en un lado y uno en el otro).

Entonces, la recurrencia se puede expresar como

${\ Displaystyle f (n) = f (n-1) + \ sum _ {i = 1} ^ {n-1} \ left (1+ \ left (ni-1 \ right) \ left (i-1 \ bien bien)}$

que se puede reducir fácilmente a

${\ Displaystyle f (n) = f (n-1) + \ sum _ {i = 1} ^ {n-1} \ left (2-n + ni-i ^ {2} \ right)}$

usando las sumas de los primeros números naturales y los primeros cuadrados, esto se combina para ${\ Displaystyle (n-1)}$${\ Displaystyle (n-1)}$

${\ Displaystyle f (n) = f (n-1) + {\ frac {1} {6}} n ^ {3} -n ^ {2} + {\ frac {17} {6}} n-2 }$

Finalmente

${\ Displaystyle f (n) = \ sum _ {k = 1} ^ {n} \ left ({\ frac {1} {6}} k ^ {3} -k ^ {2} + {\ frac {17 } {6}} k-2 \ right) +1}$ con ${\ Displaystyle f (0) = 1}$

cuyos rendimientos

${\ Displaystyle f (n) = {\ frac {n} {24}} (n ^ {3} -6n ^ {2} + 23n-18) +1}$

Método combinatorio y topológico

El lema afirma que el número de regiones es máximo si todas las intersecciones "internas" de los acordes son simples (exactamente dos acordes pasan por cada punto de intersección en el interior). Este será el caso si los puntos del círculo se eligen " en posición general ". Bajo este supuesto de "intersección genérica", el número de regiones también se puede determinar de una manera no inductiva, utilizando la fórmula para la característica de Euler de un gráfico plano conectado (visto aquí como un gráfico incrustado en la 2 esfera S ² ).

Un gráfico plano determina una descomposición de celda del plano con caras F (celdas bidimensionales), aristas E (celdas unidimensionales) y vértices V (celdas de dimensión 0). Como la gráfica está conectada, la relación de Euler para la esfera bidimensional S ²

${\ Displaystyle \, V-E + F = 2}$

sostiene. Vea el diagrama (el círculo junto con todos los acordes) de arriba como un gráfico plano. Si se pueden encontrar las fórmulas generales para V y E , también se puede derivar la fórmula para F , lo que resolverá el problema.

Sus vértices incluyen los n puntos en el círculo, denominados vértices exteriores, así como los vértices interiores, las intersecciones de distintos acordes en el interior del círculo. La suposición de "intersección genérica" ​​hecha anteriormente garantiza que cada vértice interior es la intersección de no más de dos cuerdas.

Por tanto, la tarea principal para determinar V es encontrar el número de vértices interiores. Como consecuencia del lema, dos acordes que se crucen determinarán de forma única un vértice interior. Estos acordes, a su vez, están determinados de forma única por los cuatro puntos finales correspondientes de los acordes, que son todos vértices exteriores. Cualquiera de las cuatro vértices exteriores determinan un cuadrilátero cíclico , y todos los cuadriláteros cíclicos son convexas cuadriláteros , por lo que cada conjunto de cuatro vértices exteriores tienen exactamente un punto de intersección formada por sus diagonales (acordes). Además, por definición, todos los vértices interiores están formados por cuerdas que se cruzan.

Por lo tanto, cada vértice interior está determinado de forma única por una combinación de cuatro vértices exteriores, donde el número de vértices interiores viene dado por

${\ displaystyle V _ {\ text {interior}} = {n \ choose 4},}$

y entonces

${\ Displaystyle V = V _ {\ text {exterior}} + V _ {\ text {interior}} = n + {n \ elige 4}.}$

Las aristas incluyen los n arcos circulares que conectan pares de vértices exteriores adyacentes, así como los segmentos de línea de cuerdas (descritos a continuación) creados dentro del círculo por la colección de cuerdas. Dado que hay dos grupos de vértices: exterior e interior, los segmentos de línea cordal se pueden clasificar en tres grupos:

1. Bordes directamente (no cortados por otros acordes) conectando dos vértices exteriores. Son cuerdas entre vértices exteriores adyacentes y forman el perímetro del polígono. Hay n tales aristas.
2. Bordes que conectan dos vértices interiores.
3. Aristas que conectan un vértice interior y exterior.

Para encontrar el número de aristas en los grupos 2 y 3, considere cada vértice interior, que está conectado a exactamente cuatro aristas. Esto produce

${\ Displaystyle 4 {n \ Choose 4}}$

bordes. Dado que cada borde está definido por dos vértices de punto final, solo se enumeraron los vértices interiores, los bordes del grupo 2 se cuentan dos veces mientras que los bordes del grupo 3 se cuentan solo una vez.

Cada acorde que es cortado por otro (es decir, acordes que no están en el grupo 1) debe contener dos aristas del grupo 3, sus segmentos de acordes iniciales y finales. Como los acordes están determinados únicamente por dos vértices exteriores, hay

${\ Displaystyle 2 \ left ({n \ Choose 2} -n \ right)}$

grupo 3 aristas. Esto es el doble del número total de acordes que no son miembros del grupo 1.

La suma de estos resultados dividida por dos da el número combinado de aristas en los grupos 2 y 3. Sumando las n aristas del grupo 1, y las n aristas de arco circular lleva el total a

${\ Displaystyle E = {\ frac {4 {n \ elige 4} +2 \ left ({n \ elige 2} -n \ right)} {2}} + n + n = 2 {n \ elige 4} + {n \ elija 2} + n.}$

Sustituyendo V y E en la relación de Euler resuelta para F , se obtiene ${\ Displaystyle \, F = E-V + 2,}$

${\ Displaystyle F = {n \ elige 4} + {n \ elige 2} +2.}$

Dado que una de estas caras es el exterior del círculo, el número de regiones r _G dentro del círculo es F - 1, o

${\ Displaystyle r_ {G} = {n \ elige 4} + {n \ elige 2} +1,}$

que resuelve

${\ Displaystyle r_ {G} = {\ frac {n!} {(n-4)! 4!}} + {\ frac {n!} {(n-2)! 2!}} + 1}$

que produce el mismo polinomio cuártico obtenido mediante el método inductivo

${\ Displaystyle r_ {G} = {\ frac {1} {24}} n (n ^ {3} -6n ^ {2} + 23n-18) +1}$

Ver también

• Secuencia del catering perezoso : donde n es el número de cortes rectos

Referencias

• Conway, JH y Guy, RK "Cuántas regiones". En El libro de los números . Nueva York: Springer-Verlag, págs. 76–79, 1996.
• Weisstein, Eric W. "División de círculos por acordes" . MathWorld .
• http://www.arbelos.co.uk/Papers/Chords-regions.pdf