HOME

TheInfoList



OR:

The number of and for first 6 terms of Moser's circle problem In
geometry Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...
, the problem of dividing a circle into areas by means of an inscribed
polygon In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed ''polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two toge ...
with ''n'' sides in such a way as to ''maximise'' the number of areas created by the edges and
diagonal In geometry, a diagonal is a line segment joining two vertices of a polygon or polyhedron, when those vertices are not on the same edge. Informally, any sloping line is called diagonal. The word ''diagonal'' derives from the ancient Greek δ ...
s, sometimes called Moser's circle problem, has a solution by an inductive method. The greatest possible number of regions, , giving the sequence 1, 2, 4, 8, 16, 31, 57, 99,
163 Year 163 ( CLXIII) was a common year starting on Friday (link will display the full calendar) of the Julian calendar. At the time, it was known as the Year of the Consulship of Laelianus and Pastor (or, less frequently, year 916 '' Ab urbe con ...
, 256, ... (). Though the first five terms match the
geometric progression In mathematics, a geometric progression, also known as a geometric sequence, is a sequence of non-zero numbers where each term after the first is found by multiplying the previous one by a fixed, non-zero number called the ''common ratio''. For e ...
, it diverges at , showing the risk of generalising from only a few observations.


Lemma

If there are ''n'' points on the circle and one more point is added, ''n'' lines can be drawn from the new point to previously existing points. Two cases are possible. In the first case (a), the new line passes through a point where two or more old lines (between previously existing points) cross. In the second case (b), the new line crosses each of the old lines in a different point. It will be useful to know the following fact. Lemma. The new point ''A'' can be chosen so that case ''b'' occurs for each of the new lines. Proof. For the case ''a'', three points must be on one line: the new point ''A'', the old point ''O'' to which the line is drawn, and the point ''I'' where two of the old lines intersect. There are ''n'' old points ''O'', and hence finitely many points ''I'' where two of the old lines intersect. For each ''O'' and ''I'', the line ''OI'' crosses the circle in one point other than ''O''. Since the circle has infinitely many points, it has a point ''A'' which will be on none of the lines ''OI''. Then, for this point ''A'' and all of the old points ''O'', case ''b'' will be true. This lemma means that, if there are ''k'' lines crossing ''AO'', then each of them crosses ''AO'' at a different point and ''k+1'' new areas are created by the line ''AO''.


Solution


Inductive method

The lemma establishes an important property for solving the problem. By employing an
inductive proof Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ...  all hold. Informal metaphors help ...
, one can arrive at a formula for ''f''(''n'') in terms of ''f''(''n'' − 1). In the figure the dark lines are connecting points 1 through 4 dividing the circle into 8 total regions (i.e., ''f''(4) = 8). This figure illustrates the inductive step from ''n'' = 4 to ''n'' = 5 with the dashed lines. When the fifth point is added (i.e., when computing ''f''(5) using ''f''(4)), this results in four new lines (the dashed lines in the diagram) being added, numbered 1 through 4, one for each point that they connect to. The number of new regions introduced by the fifth point can therefore be determined by considering the number of regions added by each of the 4 lines. Set ''i'' to count the lines being added. Each new line can cross a number of existing lines, depending on which point it is to (the value of ''i''). The new lines will never cross each other, except at the new point. The number of lines that each new line intersects can be determined by considering the number of points on the "left" of the line and the number of points on the "right" of the line. Since all existing points already have lines between them, the number of points on the left multiplied by the number of points on the right is the number of lines that will be crossing the new line. For the line to point ''i'', there are :''n'' − ''i'' − 1 points on the left and :''i'' − 1 points on the right, so a total of : (''n'' − ''i'' − 1) (''i'' − 1) lines must be crossed. In this example, the lines to ''i'' = 1 and ''i'' = 4 each cross zero lines, while the lines to ''i'' = 2 and ''i'' = 3 each cross two lines (there are two points on one side and one on the other). So the recurrence can be expressed as :f(n)=f(n-1)+\sum^_\left(1+\left(n-i-1\right)\left(i-1\right)\right) which can be easily reduced to :f(n)=f(n-1)+\sum^_\left(2-n+ni-i^2\right) using the sums of the first (n-1) natural numbers and the first (n-1) squares, this combines to :f(n)=f(n-1)+\fracn^3-n^2+\fracn-2 Finally :f(n)=\sum^_\left(\frack^3-k^2+\frack-2\right)+1 with f(0)=1 which yields :f(n)=\frac(n^3-6n^2+23n-18)+1


Combinatorics and topology method

The lemma asserts that the number of regions is maximal if all "inner" intersections of chords are simple (exactly two chords pass through each point of intersection in the interior). This will be the case if the points on the circle are chosen " in general position". Under this assumption of "generic intersection", the number of regions can also be determined in a non-inductive way, using the formula for the
Euler characteristic In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic (or Euler number, or Euler–Poincaré characteristic) is a topological invariant, a number that describes a topological space ...
of a
connected Connected may refer to: Film and television * ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular'' * '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film * ''Connected'' (2015 TV ...
planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...
(viewed here as a graph embedded in the 2-
sphere A sphere () is a Geometry, geometrical object that is a solid geometry, three-dimensional analogue to a two-dimensional circle. A sphere is the Locus (mathematics), set of points that are all at the same distance from a given point in three ...
S 2). A planar graph determines a cell decomposition of the plane with ''F'' faces (2-dimensional cells), ''E'' edges (1-dimensional cells) and ''V'' vertices (0-dimensional cells). As the graph is connected, the Euler relation for the 2-dimensional sphere S 2 :\, V-E+F=2 holds. View the diagram (the circle together with all the chords) above as a planar graph. If the general formulas for ''V'' and ''E'' can both be found, the formula for ''F'' can also be derived, which will solve the problem. Its vertices include the ''n'' points on the circle, referred to as the exterior vertices, as well as the interior vertices, the intersections of distinct chords in the interior of the circle. The "generic intersection" assumption made above guarantees that each interior vertex is the intersection of no more than two chords. Thus the main task in determining ''V'' is finding the number of interior vertices. As a consequence of the lemma, any two intersecting chords will uniquely determine an interior vertex. These chords are in turn uniquely determined by the four corresponding endpoints of the chords, which are all exterior vertices. Any four exterior vertices determine a
cyclic quadrilateral In Euclidean geometry, a cyclic quadrilateral or inscribed quadrilateral is a quadrilateral whose vertices all lie on a single circle. This circle is called the ''circumcircle'' or ''circumscribed circle'', and the vertices are said to be ''c ...
, and all cyclic quadrilaterals are convex
quadrilateral In geometry a quadrilateral is a four-sided polygon, having four edges (sides) and four corners (vertices). The word is derived from the Latin words ''quadri'', a variant of four, and ''latus'', meaning "side". It is also called a tetragon, ...
s, so each set of four exterior vertices have exactly one point of intersection formed by their diagonals (chords). Further, by definition ''all'' interior vertices are formed by intersecting chords. Therefore each interior vertex is uniquely determined by a combination of four exterior vertices, where the number of interior vertices is given by :V_ = , and so :V = V_ + V_ = n + . The edges include the ''n''
circular arc Circular may refer to: * The shape of a circle * ''Circular'' (album), a 2006 album by Spanish singer Vega * Circular letter (disambiguation) ** Flyer (pamphlet), a form of advertisement * Circular reasoning, a type of logical fallacy * Circular ...
s connecting pairs of adjacent exterior vertices, as well as the chordal line segments (described below) created inside the circle by the collection of chords. Since there are two groups of vertices: exterior and interior, the chordal line segments can be further categorized into three groups: # Edges directly (not cut by other chords) connecting two exterior vertices. These are chords between adjacent exterior vertices, and form the perimeter of the polygon. There are ''n'' such edges. # Edges connecting two interior vertices. # Edges connecting an interior and exterior vertex. To find the number of edges in groups 2 and 3, consider each interior vertex, which is connected to exactly four edges. This yields :4 edges. Since each edge is defined by two endpoint vertices, only the interior vertices were enumerated, group 2 edges are counted twice while group 3 edges are counted once only. Every chord that is cut by another (i.e., chords not in group 1) must contain two group 3 edges, its beginning and ending chordal segments. As chords are uniquely determined by two exterior vertices, there are altogether :2\left( - n \right) group 3 edges. This is twice the total number of chords that are not themselves members of group 1. The sum of these results divided by two gives the combined number of edges in groups 2 and 3. Adding the ''n'' edges from group 1, and the ''n'' circular arc edges brings the total to :E = \frac + n + n = 2 + + n. Substituting ''V'' and ''E'' into the Euler relation solved for ''F'', \, F = E - V + 2, one then obtains : F = + + 2. Since one of these faces is the exterior of the circle, the number of regions ''r''''G'' inside the circle is ''F'' − 1, or : r_G=++1, which resolves to :r_G=\frac+\frac+1 which yields the same quartic polynomial obtained by using the inductive method :r_G=\fracn(n^3-6n^2+23n-18)+1 The fifth column of
Bernoulli's triangle Bernoulli's triangle is an array of partial sums of the binomial coefficients. For any non-negative integer ''n'' and for any integer ''k'' included between 0 and ''n'', the component in row ''n'' and column ''k'' is given by: : \sum_^k , i.e ...
(''k'' = 4) gives the maximum number of regions in the problem of dividing a circle into areas for ''n'' + 1 points, where ''n'' ≥ 4.


Application to mathematical billiards inside the circle

Considering the force-free motion of a particle inside a circle it was shown (see D. Jaud) that for specific reflection angles along the circle boundary the associated area division sequence is given by an arithmetic series.


See also

*
Lazy caterer's sequence The lazy caterer's sequence, more formally known as the central polygonal numbers, describes the maximum number of pieces of a disk (a pancake or pizza is usually used to describe the situation) that can be made with a given number of straight cut ...
– where ''n'' is the number of straight cuts


References

* Conway, J. H. and Guy, R. K. "How Many Regions." In ''The Book of Numbers''. New York: Springer-Verlag, pp. 76–79, 1996. * * http://www.arbelos.co.uk/Papers/Chords-regions.pdf {{Webarchive, url=https://web.archive.org/web/20110904063810/http://www.arbelos.co.uk/Papers/Chords-regions.pdf , date=2011-09-04 * 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 Combinatorics Circles Area