What is the maximal number of regions a circle can be divided in by segments joining $n$ points on the boundary of the circle ? Posted already on the board I think...
Problem
Source: IMO LongList 1959-1966 Problem 14
Tags: combinatorics, combinatorial geometry, counting, circles, arrangement, IMO Shortlist, IMO Longlist
02.09.2004 12:22
Let $R_n$ be the maximal number of regions for $n$ points. Clearly, this occur when any three chords are not concurrent. Let's consider the configuration with $n+1$ points, say $A_1, \ldots, A_{n+1}$ in that order around the circle. For each $i = 1, \ldots, n$ the chord $A_{n+1}A_i$ intersects each of the chords which have endpoints on the opposite sides of it, and none of the others. Since there are $i-1$ points in one side and $n-i$ on the opposite side, there are $(i-1)(n-i)$ intersections. The number of regions which have to be add with this chord is the number of intersected chord plus 1, thus : $\displaystyle R_{n+1} = R_n + \sum_{i=1}^n [(i-1)(n-i)+1] = R_n + \frac {n^3 - 3n^2 + 8n} 6$. Using that $R_1 = 1$ it follows that : $\displaystyle R_{n+1} = 1 + \sum_{i=1}^n \frac {i^3 - 3i^2 + 8i} 6$, from which we easily deduce that : $\displaystyle R_n = 1 + \frac {n(n-1)(n^2-5n+18)} {24}$. Pierre.
11.08.2022 17:56
Claim. The maximal number of regions occurs when no three of the chords are concurrent. Proof. Let $l_1$, $l_2$, and $l_3$ be three chords that concur at a single point. Then, shift $l_3$ by an arbitrarily small margin such that $l_1,l_2,l_3$ no longer concur, and the intersections and regions $l_3$ creates with all chords other than $l_1$ and $l_2$ are not affected. In this manner, the number of regions by having these chords not concur increases (by $1$), since through this shifting, a new region determined by $l_1$, $l_2$, and $l_3$ is created. Applying this logic to every set of $3$ or more chords yields the desired result. $\Box$ Now, treat the optimal configuration as a graph. We first compute the number of vertices. Observe that there is a bijection between chord intersection points inside the circle and sets of $4$ points on the circumference, because each such intersection point is the intersection of the diagonals of a quadrilateral with its vertices on the circumference, and vice versa. As a result, there are $\tbinom{n}{4}$ intersection points, and combining this with the $n$ points on the circumference gives $\tbinom{n}{4}+n$ vertices in the graph. We then compute the number of edges. There are $\tbinom{n}{2}$ chords connecting the $n$ points on the circumference, and each of the $\tbinom{n}{4}$ interior intersection points creates $2$ additional edges, because it splits each of the $2$ edges it lies on into $2$ smaller edges. As a result, there are $2\tbinom{n}{4}+\tbinom{n}{2}$ edges inside the circle, and combining this with the $n$ arcs forming the circumference yields $2\tbinom{n}{4}+\tbinom{n}{2}+n$ edges in the graph. Hence, by Euler's characteristic, $$F=E-V+2=\left(2\binom{n}{4}+\binom{n}{2}+n\right)-\left(\binom{n}{4}+n\right)+2=\binom{n}{4}+\binom{n}{2}+2,$$and subtracting the $1$ region outside of the circle gives $\boxed{\tbinom{n}{4}+\tbinom{n}{2}+1}$ regions inside the circle, as requested. $\blacksquare$