Moser's circle problem asks how many regions a circle can be divided into by choosing n {\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 n {\displaystyle n} points is given by r G = ( n 4 ) + ( n 2 ) + 1 = 1 24 ( n 4 − 6 n 3 + 23 n 2 − 18 n + 24 ) , {\displaystyle r_{G}={n \choose 4}+{n \choose 2}+1={\frac {1}{24}}(n^{4}-6n^{3}+23n^{2}-18n+24),}
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 2 n − 1 {\displaystyle 2^{n-1}} , the two sequences differ for n ≥ 6 {\displaystyle n\geq 6} . 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. 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 ( n 4 ) + ( n 2 ) + 1 {\displaystyle {\tbinom {n}{4}}+{\tbinom {n}{2}}+1} , as detailed below. By rotating the circle, it can be placed in a position in which each of the regions has a unique topmost point (with maximum y {\displaystyle y} -coordinate) and a unique bottommost point (with minimum y {\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 r {\displaystyle r} regions, there are 2 r {\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 2 ( n 4 ) {\displaystyle 2{\tbinom {n}{4}}} pairs of a region and one of its extreme points. Each chosen point borders n {\displaystyle n} regions, and is the topmost or bottommost point of all but one of them. Therefore, the chosen points take part in n ( n − 1 ) = 2 ( n 2 ) {\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
2 r = 2 ( ( n 4 ) + ( n 2 ) + 1 ) , {\displaystyle 2r=2\left({\binom {n}{4}}+{\binom {n}{2}}+1\right),}
… excerpt ends here. Continue reading the full article.
