Moser's circle problem

Moser's circle problem asks how many regions a circle can be divided into by choosing ${\displaystyle n}$ points along the circumference of the circle and joining each pair of points by a straight line. The greatest possible number of regions with ${\displaystyle n}$ points is given by ${\displaystyle r_{G}={n \choose 4}+{n \choose 2}+1}$, resulting in the sequence 1, 2, 4, 8, 16, 31, 57, 99, 163, 256, ... (sequence A000127 in the OEIS). Though the first five terms match the geometric progression ${\displaystyle 2^{n-1}}$, the two sequences differ for ${\displaystyle n\geq 6}$. As Leo Moser noted in 1949, this sequence demonstrates the risk of generalising from only a few observations.^[1]

For the number of regions to be maximized, no three diagonals should cross at the same point, for otherwise a small perturbation to the points would increase the number of regions. Triple crossings can always be avoided by choosing points one by one, starting from an empty set. At each step, only finitely many points of the circle belong to lines through one of the previously chosen points and through a crossing point of their diagonals. By avoiding this finite set of points, each successive point can be chosen in such a way that each crossing point is the crossing of only two diagonals. For any such sequence of choices, the number of regions is ${\displaystyle {\tbinom {n}{4}}+{\tbinom {n}{2}}+1}$, as detailed below.

By rotating the circle, it can be placed in a position in which no each of the regions has a unique topmost point (with maximum ${\displaystyle y}$-coordinate) and a unique bottommost point (with minimum ${\displaystyle y}$-coordinate), and in which neither the top nor the bottom point of the circle is one of the chosen points. After this rotation, if there are ${\displaystyle r}$ regions, there are ${\displaystyle 2r}$ pairs of a region and one of its two extreme points.

Each subset of four chosen points form the endpoints of exactly one pair of crossing diagonals, and their crossings each form the topmost point of one region and the bottommost point of one region. Therefore, the diagonal crossings take part in ${\displaystyle 2{\tbinom {n}{4}}}$ pairs of a region and one of its extreme points. Each chosen point borders ${\displaystyle n}$ regions, and is the topmost or bottommost point of all but one of them. Therefore, the chosen points take part in ${\displaystyle n(n-1)=2{\tbinom {n}{2}}}$ pairs of a region and one of its extreme points. Additionally, the topmost and bottommost points of the circle take part in two pairs of a region and one of its extreme points.

Putting together all of this information about the number of pairs of a region and its extreme points gives a proof by double counting that $${\displaystyle 2r=2\left({\binom {n}{4}}+{\binom {n}{2}}+1\right),}$$ equivalent to the given solution to Moser's circle problem.

John Horton Conway and Richard K. Guy provide an alternative bijective proof of the equivalent formula $${\displaystyle r={\binom {n-1}{4}}+{\binom {n-1}{3}}+{\binom {n-1}{2}}+{\binom {n-1}{1}}+{\binom {n-1}{0}},}$$ by finding a one-to-one correspondence between the regions and subsets of up to four of the chosen points, omitting one of the chosen points from all of these subsets.^[2] It is also possible to derive a formula for the number of regions from Euler's formula ${\displaystyle V-E+F=2}$ for the numbers of vertices, edges, and faces of a planar graph,^[3][4][5] or by considering the number of additional pieces created in each step when the points or diagonals are added one by one.^[6][7][8]

If the points are uniformly spaced around the circle, the number of regions is reduced for even ${\displaystyle n\geq 4}$: six points produce 30 regions instead of 31, eight points produce 88 regions instead of 99, etc.^[9]

The problem of finding the maximum number of regions into which a convex polygon with ${\displaystyle n}$ vertices can be subdivided by its diagonals differs from Moser's problem in that there are no diagonals between consecutive polygon vertices; instead the line segment between two such points is an edge of the polygon itself. Therefore the ${\displaystyle n}$ circular segments formed by these diagonals in Moser's circle problem do not appear in the polygon problem. Similar arguments to those for Moser's circle problem can be used to show that the number of regions is maximized when there is no triple crossing of diagonals, and that in this case the number of regions is^[10] $${\displaystyle {\binom {n}{4}}+{\binom {n-1}{2}}.}$$

The same sequence of numbers found in the solution of Moser's circle problem also provides the maximum number of regions that 4-dimensional space can be cut into by ${\displaystyle n-1}$ hyperplanes.^[11] As with Moser's circle problem, this has been used as an example of the risk of generalising from few observations.^[12] The corresponding sequences of numbers for subdivision of two-dimensional space by lines and three-dimensional space by planes are the lazy caterer's sequence and cake numbers, respectively.

• Pizza theorem – Equality of areas of a sliced disk

• Jaud, D. "Integer Sequences from Circle Divisions by Rational Billiard Trajectories". In "ICGG 2022 - Proceedings of the 20th International Conference on Geometry and Graphics", DOI: 10.1007/978-3-031-13588-0_8

• Weisstein, Eric W. "Circle Division by Chords". MathWorld.
• http://www.arbelos.co.uk/Papers/Chords-regions.pdf Archived 2011-09-04 at the Wayback Machine