Moser's circle problem

resulting in the sequence 1, 2, 4, 8, 16, 31, 57, 99, 163, 256, ... . Though the first five terms match the geometric progression. As Leo Moser noted in 1949, this sequence demonstrates the risk of generalising from only a few observations.

Solution

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, as detailed below.

pairs of a region and one of its two extreme points.

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 equivalent to the given solution to Moser's circle problem.

John Horton Conway and Richard K. Guy provide an alternative bijective proof 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. It is also possible to derive a formula for the number of regions from Euler's formula for the numbers of vertices, edges, and faces of a planar graph, or by considering the number of additional pieces created in each step when the points or diagonals are added one by one.

Related problems

If the points are uniformly spaced around the circle, the number of regions is reduced for even: six points produce 30 regions instead of 31, eight points produce 88 regions instead of 99, etc.

The problem of finding the maximum number of regions into which a convex polygon 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

the first few terms are 0, 0, 1, 4, 11, 25, 50, 91, 154, 246, ... .

hyperplanes. As with Moser's circle problem, this has been used as an example of the risk of generalising from few observations. 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.

See also

References

Further reading

• 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

External links

• http://www.arbelos.co.uk/Papers/Chords-regions.pdf