El problema del círculo de Moser

El problema del círculo de Moser pregunta en cuántas regiones se puede dividir un círculo eligiendo${\displaystyle n}$puntos a lo largo de la circunferencia del círculo y uniendo cada par de puntos por una línea recta. El mayor número posible de regiones con${\displaystyle n}$Los puntos se dan por${\displaystyle r_{G}={n \choose 4}+{n \choose 2}+1}$lo que da como resultado la secuencia 1, 2, 4, 8, 16, 31, 57, 99, 163, 256, ... (secuencia A000127 en el OEIS ) . Aunque los primeros cinco términos coinciden con la progresión geométrica .${\displaystyle 2^{n-1}}$, las dos secuencias difieren en${\displaystyle n\geq 6}$Como señaló Leo Moser en 1949, esta secuencia demuestra el riesgo de generalizar a partir de solo unas pocas observaciones. ^{[ 1 ]}

Para maximizar el número de regiones, no deben cruzarse tres diagonales en el mismo punto, ya que de lo contrario una pequeña perturbación en los puntos aumentaría el número de regiones. Los cruces triples siempre se pueden evitar eligiendo puntos uno por uno, comenzando desde un conjunto vacío . En cada paso, solo un número finito de puntos del círculo pertenecen a líneas que pasan por uno de los puntos elegidos previamente y por un punto de intersección de sus diagonales. Al evitar este conjunto finito de puntos, cada punto sucesivo se puede elegir de tal manera que cada punto de intersección sea la intersección de solo dos diagonales. Para cualquier secuencia de elecciones de este tipo, el número de regiones es${\displaystyle {\tbinom {n}{4}}+{\tbinom {n}{2}}+1}$, como se detalla a continuación.

Al girar el círculo, se puede colocar en una posición en la que ninguna de las regiones tenga un punto superior único (con máximo${\displaystyle y}$-coordenada) y un único punto inferior (con mínimo${\displaystyle y}$-coordenada), y en la que ni el punto superior ni el inferior del círculo son uno de los puntos elegidos. Después de esta rotación, si hay${\displaystyle r}$regiones, hay${\displaystyle 2r}$pares formados por una región y uno de sus dos puntos extremos.

Cada subconjunto de cuatro puntos elegidos forma los extremos de exactamente un par de diagonales que se cruzan, y sus cruces forman cada uno el punto más alto de una región y el punto más bajo de una región. Por lo tanto, los cruces diagonales participan en${\displaystyle 2{\tbinom {n}{4}}}$pares de una región y uno de sus puntos extremos. Cada punto elegido limita con${\displaystyle n}$regiones, y es el punto más alto o más bajo de todas menos una de ellas. Por lo tanto, los puntos elegidos participan en${\displaystyle n(n-1)=2{\tbinom {n}{2}}}$pares de una región y uno de sus puntos extremos. Además, los puntos más alto y más bajo del círculo participan en dos pares de una región y uno de sus puntos extremos.

Al reunir toda esta información sobre el número de pares de una región y sus puntos extremos, se obtiene una prueba mediante doble conteo de que $${\displaystyle 2r=2\left({\binom {n}{4}}+{\binom {n}{2}}+1\right),}$$ equivalente a la solución dada al problema del círculo de Moser.

John Horton Conway y Richard K. Guy proporcionan una demostración biyectiva alternativa de la fórmula equivalente.$${\displaystyle r={\binom {n-1}{4}}+{\binom {n-1}{3}}+{\binom {n-1}{2}}+{\binom {n-1}{1}}+{\binom {n-1}{0}},}$$ al encontrar una correspondencia uno a uno entre las regiones y subconjuntos de hasta cuatro de los puntos elegidos, omitiendo uno de los puntos elegidos de todos estos subconjuntos. ^{[ 2 ]} También es posible derivar una fórmula para el número de regiones a partir de la fórmula de Euler.${\displaystyle V-E+F=2}$para el número de vértices, aristas y caras de un grafo planar , ^{[ 3 ] [ 4 ] [ 5 ]} o considerando el número de piezas adicionales creadas en cada paso cuando los puntos o diagonales se agregan uno por uno. ^{[ 6 ] [ 7 ] [ 8 ]}

Si los puntos están espaciados uniformemente alrededor del círculo, el número de regiones se reduce para incluso${\displaystyle n\geq 4}$: seis puntos producen 30 regiones en lugar de 31, ocho puntos producen 88 regiones en lugar de 99, etc. ^{[ 9 ]}

El problema de encontrar el número máximo de regiones en las que se puede dividir un polígono convexo con${\displaystyle n}$Los vértices se pueden subdividir por sus diagonales difiere del problema de Moser en que no hay diagonales entre vértices de polígonos consecutivos; en cambio, el segmento de línea entre dos de esos puntos es una arista del propio polígono. Por lo tanto,${\displaystyle n}$Los segmentos circulares formados por estas diagonales en el problema del círculo de Moser no aparecen en el problema del polígono. Se pueden usar argumentos similares a los del problema del círculo de Moser para demostrar que el número de regiones se maximiza cuando no hay cruce triple de diagonales, y que en este caso el número de regiones es ^{[ 10 ].}$${\displaystyle {\binom {n}{4}}+{\binom {n-1}{2}}.}$$

La misma secuencia de números que se encuentra en la solución del problema del círculo de Moser también proporciona el número máximo de regiones en las que se puede dividir el espacio de 4 dimensiones.${\displaystyle n-1}$hiperplanos . ^{[ 11 ]} Al igual que con el problema del círculo de Moser, esto se ha utilizado como ejemplo del riesgo de generalizar a partir de pocas observaciones. ^{[ 12 ]} Las secuencias de números correspondientes para la subdivisión del espacio bidimensional por líneas y del espacio tridimensional por planos son la secuencia del proveedor perezoso y los números de pastel , respectivamente.

• Teorema de la pizza : Igualdad de áreas de discos cortados 

• Jaud, D. "Secuencias de enteros a partir de divisiones de círculos mediante trayectorias de billar racionales". En "ICGG 2022 - Actas de la 20.ª Conferencia Internacional sobre Geometría y Gráficos", DOI: 10.1007/978-3-031-13588-0_8

• Weisstein, Eric W. "División de círculos por cuerdas" . MathWorld .
• http://www.arbelos.co.uk/Papers/Chords-regions.pdf Archivado el 4 de septiembre de 2011 en Wayback Machine