Poland 2

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

w

14 users

TOPICS

No tags match your search

M

No tags match your search

M

Poland 2

G H J

Reveal topic tags

combinatorial geometry

L

G H BBookmark kLocked kLocked NReply

Source: IMO LongList 1959-1966 Problem 14

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3647 posts

orl

#1 h Sep 1, 2004, 11:16 PM • 2 Y

Y by Adventure10, Mango247

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...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3004 posts

#2 h Sep 2, 2004, 9:22 AM • 3 Y

Y by khan.academy, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5417 posts

#3 h Aug 11, 2022, 2:56 PM • 1 Y

Y by ihatemath123

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$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a