Vertices of a convex polygon if and only if m(S) = f(n)

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

15 users

TOPICS

No tags match your search

M

No tags match your search

M

Vertices of a convex polygon if and only if m(S) = f(n)

G H J

Reveal topic tags

combinatorial geometry

L

G H BBookmark kLocked kLocked NReply

Source: IMO Shortlist 2000, C3

The post below has been deleted. Click to close.

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

3647 posts

orl

#1 h Aug 10, 2008, 12:26 AM • 6 Y

Y by Adventure10, junioragd, and 4 other users

Let $n \geq 4$ be a fixed positive integer. Given a set $S = \{P_1, P_2, \ldots, P_n\}$ of $n$ points in the plane such that no three are collinear and no four concyclic, let $a_t,$ $1 \leq t \leq n,$ be the number of circles $P_iP_jP_k$ that contain $P_t$ in their interior, and let $m(S)=a_1+a_2+\cdots + a_n.$ Prove that there exists a positive integer $f(n),$ depending only on $n,$ such that the points of $S$ are the vertices of a convex polygon if and only if $m(S) = f(n).$

This post has been edited 1 time. Last edited by djmathman, Oct 3, 2016, 3:25 AM
Reason: changed formatting to match imo compendium

Z K Y

The post below has been deleted. Click to close.

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

Thjch Ph4 Trjnh

205 posts

Thjch Ph4 Trjnh

#2 h Jul 3, 2009, 6:42 AM • 4 Y

Y by Adventure10, Mango247, and 2 other users

$f(n) = 2.(_4^n)$

Z K Y

The post below has been deleted. Click to close.

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

4464 posts

Myth

#3 h Jul 3, 2009, 8:15 PM • 4 Y

Y by Ali3085, Adventure10, Mango247, and 1 other user

It is strange to see such an easy and evident problem in IMO SL.

Z K Y

The post below has been deleted. Click to close.

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

801 posts

#4 h Dec 25, 2010, 5:45 AM • 12 Y

Y by Catalanfury, Vaijan_Mama, k12byda5h, DCMaths, Adventure10, Mango247, Stuffybear, winniep008hfi, and 4 other users

We claim that the function $f(n)=2 \binom{n}{4}$ satisfies the requirements.

Let the score $s(a,b,c,d)$ of the four points $P_a$ , $P_b$ , $P_c$ and $P_d$ be the number of points $P_i$ where $i \in \{a,b,c,d \}$ such that $P_i$ is properly contained in the circle passing through the remaining three points. Observe that

$m(S) = \sum_{1 \le a<b<c<d \le n} s(a,b,c,d)$

First we prove the following lemma.

Lemma 1. The score of a convex quadrilateral $2$ .

Proof. Let the vertices of the convex quadrilateral be denoted as $A, B, C$ and $D$ . We have that point $D$ lies within the circumcircle of $\triangle{ABC}$ if and only if

$\angle{ABC} > 180 - \angle{ADC} \quad \Leftrightarrow \quad \angle{ABC} + \angle{ADC} > 180$

Therefore if $D$ lies within the circumcircle of $\triangle{ABC}$ , it also follows by symmetry that $B$ lies within the circumcircle of $\triangle{ADC}$ . If not, then since the sum of the interior angles of $ABCD$ is $360$ ,

$\angle{ABC} + \angle{ADC} < 180 \quad \Rightarrow \quad \angle{BAD} + \angle{ACD} > 180$

Therefore $A$ lies within the circumcircle of $\triangle{BCD}$ and $C$ lies within the circumcircle of $\triangle{ABD}$ . In both cases, the score of $ABCD$ is equal to $2$ .

Lemma 2. The score of a concave quadrilateral is $1$ .

Proof. Let $ABCD$ denote the concave quadrilateral. Without the loss of generality, let $A$ be such that interior angle $\angle{BAC} > 180$ . It follows that $A$ lies in the interior of triangle $\triangle{BCD}$ . Therefore, the circumcircle of $\triangle{BCD}$ contains $A$ . However, none of the remaining three circles passing through three of the points $A, B, C$ and $D$ contain the remaining point. Hence the score of $ABCD$ is equal to $1$ .

If Direction. If the vertices of $S$ form a convex $n$ -gon, then each quadrilateral formed by four distinct points in $S$ is a convex quadrilateral and therefore

$m(S) = \sum_{1 \le a<b<c<d \le n} s(a,b,c,d) = 2 \binom{n}{4}$

Only If Direction. If the vertices of $S$ form a concave $n$ -gon, then at least one of the quadrilaterals formed by four distinct points in $S$ is a concave quadrilateral and therefore

$m(S) = \sum_{1 \le a<b<c<d \le n} s(a,b,c,d) < 2 \binom{n}{4}$

The function $f(n)=2 \binom{n}{4}$ therefore satisfies that $m(S)=f(n)$ if and only if the points in $S$ are the vertices of a convex polygon.

Z K Y

The post below has been deleted. Click to close.

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

151 posts

JackXD

#5 h Jan 7, 2016, 4:19 PM • 1 Y

Y by Adventure10

Lemma Every quadrilateral $S$ satisfies $m(S) \le 2$ with equality if and only if it is convex,

Proof:If a quadrilateral $ABCD$ is convex then one out of $\angle{ABC}+\angle{ADC}$ and $\angle{DAB}+\angle{DCB}$ is greater than $\pi$ and the other is less than $\pi$ .This implies $m(S)=2$ .One the other hand if it is concave then clearly $m(S)=1$

Back to our main problem.If S forms a convex polygon then every quadrilateral $P_{i}P_{j}P_{k}P_{l}$ contributes $1$ to two of $a_{i},a_{j},a_{k}$ and $a_{l}$ (from the lemma) and thus contributes two to $m(S)$ .This immediately implies $f(n)=2\binom{n}{4}$

Now let $m(S)=f(n)=2\binom{n}{4}$ .Each quadrilateral $P_{i}P_{j}P_{k}P_{l}$ contributes atmost $2$ to $f(n)$ and thus $m(S) \le 2\binom{n}{4}$ .As there is equality,we have that each quadrilateral contributes exactly $2$ to $f(n)$ ,hence from the lemma every quadrilateral is convex,implying that $S$ forms a convex polygon.

This post has been edited 3 times. Last edited by JackXD, Jan 7, 2016, 4:22 PM
Reason: xx

Z K Y

The post below has been deleted. Click to close.

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

1576 posts

#6 h Aug 11, 2019, 11:58 PM • 2 Y

Y by Adventure10, Mango247

Note that given any 4 points, they add 2 to the count if their convex hull is a quadrilateral, and 1 otherwise. So, $f(n)=2\binom{n}{2}$ , with equality achieved iff all quadruplets of points form convex quadrilaterals. However, if there exists a point $P_i$ inside the convex hull $Q_1,Q_2,\ldots,Q_k$ , then it must be in one of the triangles $Q_1Q_2Q_3$ , $Q_1Q_3Q_4,\ldots Q_1Q_{k-1}Q_k$ , which cover the convex hull. So, there exist 4 points whose convex hull is a triangle. Therefore, the only way equality is reached is if all points are on the convex hull, as desired.

Z K Y

The post below has been deleted. Click to close.

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

830 posts

niyu

#7 h Jun 26, 2020, 10:31 PM

Y by

The key idea is to consider four-tuples.

Lemma: If $ABCD$ is a non-cyclic convex quadrilateral, $m(ABCD) = 2$ .

Proof: Suppose $ABCD$ is convex and non-cyclic. Note that $\angle ABC + \angle ADC \neq \angle BCD + \angle BAD \neq 180^\circ$ . Hence, exactly one of these two sums is greater than $180^\circ$ . WLOG, suppose $\angle ABC + \angle ADC > 180^\circ$ and $\angle BCD + \angle BAD < 180^\circ$ . Since $\angle ABC > 180^\circ - \angle ADC$ it follows that $B$ lies within $(ADC)$ . Similarly, $D$ lies within $(ABC)$ . Meanwhile, since $\angle BCD < 180^\circ - \angle BAD$ , it follows that $A$ does not lie within $(BCD)$ , and similarly, $C$ does not lie within $(ABD)$ . This implies that $m(ABCD) = 2$ , proving the lemma. $\blacksquare$

Lemma: If $ABCD$ is a concave quadrilateral, $m(ABCD) = 1$ .

Proof: Say $\angle BAD > 180^\circ$ . Since $A$ and $C$ both lie on the same side of $\overline{BD}$ , and $\angle BCD < \angle BAD$ , it follows that $C$ does not lie within $(ABD)$ , while $A$ lies within $(BCD)$ . Meanwhile, since $\angle ABC + \angle ADC < 180^\circ$ , by the same argument as in the previous lemma we find that $B$ does not lie within $(ACD)$ and that $D$ does not lie within $(ABC)$ . Hence, $m(ABCD) = 1$ . $\blacksquare$

We now return to the given problem. We claim that $m(S) \leq 2\binom{n}{4}$ , and that equality holds iff the points of $S$ form a convex quadrilateral. Indeed, as no four points in $S$ are concyclic, we have
$\begin{align*} m(S) &= \sum_{1 \leq w < x < y < z \leq n} m(P_wP_xP_yP_z) \\ &\leq \sum_{1 \leq w < x < y < z \leq n} 2 \\ &\leq 2\binom{n}{4}. \end{align*}$ Equality holds here iff each of the quadrilaterals $P_wP_xP_yP_z$ is convex, which occurs iff the points of $S$ form a cyclic quadrilateral. This completes the proof. $\Box$

Z K Y

The post below has been deleted. Click to close.

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

1449 posts

#8 h Jan 18, 2022, 10:45 PM

Y by

Rather easy for a C3.

All angles are in degrees.

Claim: Suppose $Q$ consists of four points $A,B,C,D$ . Then $m(Q)$ is $2$ if $A,B,C,D$ form a convex quadrilateral and $1$ otherwise.
Proof. Notice that if $A,B,C,D$ form a convex quadrilateral, then $D$ appears inside the circumcircle of $ABC$ , $\angle D$ must be greater than $180-\angle B$ , which is equivalent to $\angle B + \angle D >180$ . Since exactly one opposite pair of angles sum to greater than $180$ degrees, there will be exactly two points that are contained in the circumcircle of the other three.

If $A,B,C,D$ are not convex, WLOG let $A,B,C$ be the convex hull. Then it is clear that the only point that is contained in the circumcircle of the other three is $D$ . $\blacksquare$

The key step is to notice that $m(S)=\sum_{1\le a<b<c<d\le n} m\left(\{P_a,P_b,P_c,P_d\}\right)$ because both quantities count the amount of ordered pairs containing a single point of $S$ and a set of three points in $S$ , with all four points distinct, such that the single point is inside the circumcircle of the three points.

Using our claim, $m(S)$ must be equal to twice the number of four-point subsets of $S$ that consist of points forming a convex quadrilateral plus the four-point subsets of $S$ that do not. Moreover, every subset of four points form a convex quadrilateral iff $S$ does, so $m(S)=2\binom{n}{4}$ iff $S$ forms a convex quadrilateral. We are done.

This post has been edited 1 time. Last edited by bluelinfish, Jan 18, 2022, 10:45 PM

Z K Y

The post below has been deleted. Click to close.

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

awesomeming327.

1738 posts

awesomeming327.

#9 h Dec 30, 2022, 2:14 PM • 3 Y

Y by Mango247, Mango247, Mango247

Let $m(\{a,b,c,d\})$ be the number $m(S)$ for the quadrilateral $P_aP_bP_cP_d.$ It is easy to see that $m(S)$ is the sum of $m(\{a,b,c,d\})$ for all choices of subset $\{a,b,c,d\} \subseteq S$ . Note that $(P_aP_bP_c)$ contains $P_d$ if only $P_d$ lies inside of the angle $P_aP_bP_c$ and $\angle P_b+\angle P_d> 180^\circ.$ Clearly, when $P_aP_bP_cP_d$ then $m(a,b,c,d)=2$ and when it is nonconvex $m(a,b,c,d)=1$ . Therefore, $m(S)=2\tbinom{n}4$ if and only if $S$ is convex.

Z K Y

The post below has been deleted. Click to close.

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

4191 posts

#10 h May 5, 2024, 5:29 AM

Y by

Note that by swapping the order of summation, $m(S)$ is equal to the number of quadruples of points $(A,B,C,D)$ where $D$ is inside $(ABC)$ and $A,B,C$ are unordered.

Claim: Each set of 4 points contributes $2$ if they are convex, and $1$ if they are not.

If $ABCD$ is convex and non-cyclic, then we either have $\angle A+\angle C>180$ or $\angle B+\angle D>180$ but not both. However, since $A$ is inside $(BCD)$ if and only if $\angle A+\angle C>180$ , etc, the convex quadriateral contributes $2$ . If $D$ is inside $\triangle ABC$ , then $D$ will be inside $(ABC)$ but nothing else works.

Thus, the maximum possible value of $m(S)$ is $2{n\choose 4}$ , with equality if and only if each quadrilateral is convex, which is the same as saying the entire set is convex. We are done as $f(n)=2{n\choose 4}$ .

Z K Y

The post below has been deleted. Click to close.

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

7585 posts

#11 h May 5, 2024, 1:55 PM

Y by

For any four points $S'=\{P_a,P_b,P_c,P_d\}$ count the value $m(S')$ . Notice this is either $2$ if the convex hull is a quadrilateral (i.e. the points form a convex polygon) and $1$ if the convex hull is a triangle (i.e. there is an interior point).

Clearly $f(n)$ is the sum of $m(S')$ over all such $S'$ . Hence the maximum occurs if every convex hull of four points is a quadrilateral. If the points of $S$ are the vertices of a convex polygon this occurs. If the points of $S$ are not the vertices of a convex polygon then triangulate the convex hull. Any interior point is contained in a triangle and for these four points we have $m(S')=1$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

195 posts

onyqz

#12 h Dec 29, 2024, 1:27 AM

Y by

storage
solution

Z K Y

The post below has been deleted. Click to close.

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

575 posts

#13 h Apr 24, 2025, 4:04 AM

Y by

Observe that in any $4$ points $A, B, C, D,$ if they form a convex polygon there are $2$ pairs of the form $(i, \omega)$ where $i$ is a point from $A, B, C, D$ and $\omega$ is the circumcircle of the other points. However if they form a non-convex polygon there is $1$ only.

Clearly, if we consider all quadruples of points from our $n$ points, and sum up the number of valid pairs, every point, along with a circumcircle it lies in, is counted. In addition, the point and circumcircle pair uniquely determines which quadruple it was counted in, meaning that this count yields a injection and surjection to $m(S),$ so there is a bijection.

Therefore if $x$ quadruples are convex and $y$ are concave, $m(S) = 2x+y.$ But $x+y=\binom{n}{4}$ so $m(S)=\binom{n}{4}+x,$ and the desired result follows. QED

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a