Points and triangles in the plane

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

16 users

TOPICS

No tags match your search

M

No tags match your search

M

Points and triangles in the plane

G H J

Reveal topic tags

combinatorial geometry

Brazilian Math Olympiad

Brazilian Math Olympiad 2018

L

G H BBookmark kLocked kLocked NReply

Source: Brazilian Mathematical Olympiad 2018 - Q6

The post below has been deleted. Click to close.

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

168 posts

#1 h Nov 16, 2018, 4:05 PM • 10 Y

Y by UK2019Project, anantmudgal09, rcorreaa, rkm0959, lminsl, nguyendangkhoa17112003, Aarth, kiyoras_2001, Adventure10, Mango247

Consider $4n$ points in the plane, with no three points collinear. Using these points as vertices, we form $\binom{4n}{3}$ triangles. Show that there exists a point $X$ of the plane that belongs to the interior of at least $2n^3$ of these triangles.

Z K Y

The post below has been deleted. Click to close.

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

5850 posts

#2 h Nov 16, 2018, 6:08 PM • 13 Y

Y by rkm0959, stroller, DanDumitrescu, ZeusDM, nguyendangkhoa17112003, Aarth, kiyoras_2001, lminsl, yayups, edfearay123, wateringanddrowned, CyclicISLscelesTrapezoid, Adventure10

Let $S$ be the set of $4n$ points.

1. Let $T$ be the set of all lines through the origin. For each $\ell \in T$ , let $f(\ell)$ be a line parallel to $\ell$ that does not pass through any point in $S$ and has $2n$ points of $S$ on each side. Such an $f(\ell)$ exists for each $\ell$ since we can move the line continuously in the plane and have the number of points on each side of the line vary continuously in the discrete sense.

2. Fix an $\ell \in T$ . Let $m$ be a variable line in $T$ that starts as $\ell$ and rotates clockwise continuously until it becomes $\ell$ again. At any time, $f(\ell)$ , $f(m)$ split the plane into four sections, and the number of points in each section varies continuously in the discrete sense. Initially the number of points in each section is $0, 2n, 0, 2n$ , and at the end it is $2n, 0, 2n, 0$ . This means there exists some line $m'$ such that $f(\ell)$ and $f(m')$ split the plane into four sections each with exactly $n$ points.

3. Choose $X$ to be the intersection of $f(\ell)$ and $f(m')$ . Consider each of the $n^4$ ways to choose one point from each of the four sections formed by $f(\ell)$ and $f(m')$ . These four points form four triangles. Exactly two of the four triangles contain $X$ . This method of counting will obtain each triangle exactly $n$ times. This gives a total of $n^4 \cdot 2 / n = 2n^3$ triangles containing $X$ .

Z K Y

The post below has been deleted. Click to close.

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

137 posts

Aarth

#3 h Nov 26, 2019, 3:39 PM • 2 Y

Y by Adventure10, Mango247

MellowMelon wrote:

2. Fix an $\ell \in T$ . Let $m$ be a variable line in $T$ that starts as $\ell$ and rotates clockwise continuously until it becomes $\ell$ again. At any time, $f(\ell)$ , $f(m)$ split the plane into four sections, and the number of points in each section varies continuously in the discrete sense. Initially the number of points in each section is $0, 2n, 0, 2n$ , and at the end it is $2n, 0, 2n, 0$ . This means there exists some line $m'$ such that $f(\ell)$ and $f(m')$ split the plane into four sections each with exactly $n$ points.

Why does the number of points in each section vary continuously?

This post has been edited 1 time. Last edited by Aarth, Nov 26, 2019, 3:51 PM

Z K Y

The post below has been deleted. Click to close.

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

56 posts

#4 h Nov 29, 2019, 9:20 PM • 2 Y

Y by wateringanddrowned, Adventure10

Solution. part

Z K Y

The post below has been deleted. Click to close.

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

1065 posts

Eyed

#5 h Dec 23, 2021, 5:59 PM

Y by

I claim there exists two lines, $\ell_{1}, \ell_{2}$ , such that the $4$ regions divided by $\ell_1, \ell_2$ each contains $n$ points. Define $S$ as the set of the $4n$ points.

Let $\ell_{1}$ be an arbitrary balancing line, so each side of $\ell_{1}$ contains $2n$ points. Then, consider a point $P\in \ell_{1}$ , and consider the line $\ell$ going through $P$ that will have $n$ points on its left side, and $n$ points on the right side of $\ell_{1}$ . If we put $P$ at the very beginning of line $\ell_{1}$ , then the amount of points on the left side of $\ell_{1}$ and the left side of $\ell$ is $2n$ . However, moving $P$ to the very end of line $\ell_{1}$ gives $0$ points on the lefts ide of $\ell_{1}, \ell$ . Thus, since by moving $P$ , at each step we change at most $1$ in the number of points on the left side of $\ell, \ell_1$ , this means at some point, there are $n$ points on the left side of $\ell, \ell_{1}$ . Letting $\ell_2 = \ell$ gives the desired result.

Now, if $O = \ell_1\cap \ell_2$ , we can choose $O$ such that it does not lie on any of the lines joining $2$ points in $S$ . Consider the four regions $A,B,C,D$ , each with $n$ points, and in clockwise order (so $A,C$ are opposite, same with $B,D$ ). Now, for each $n^2$ pairs of points in $A,C$ , if $E\in A, F\in C$ , then either for any point $X\in B$ , we have $O\in \triangle EFX$ , or for any point in $Y\in D$ we have $O\in \triangle EFY$ (this is because either $O$ lies above or below line $EF$ . Therefore, there are $n^3$ triangles that contain $O$ with two vertices in $A,C$ . Similarly, there are $n^3$ triangles that contain $O$ with two vertices in $B,D$ , so we conclude that there are at least $2n^3$ triangles that $O$ is a part of.

Z K Y

The post below has been deleted. Click to close.

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

577 posts

#6 h Dec 23, 2023, 6:18 PM

Y by

Let $S$ be the set of $4n$ points in the plane.

Claim: There exist lines $\ell_1$ and $\ell_2$ that divide the plane into $4$ regions with $n$ points contained in each region and no points on either line.
Proof. Consider all of the lines through any two points of $S$ , and take $\ell$ to be a line parallel to none of these lines. Realize that if we first take it to be arbitrarily far away from the points in $S$ , and then translate it in the direction closer to the points, then the number of points on the side that initially has no points starts with $0$ and increases by exactly $1$ whenever it increases. Since it eventually reaches $4n$ points, we can move it to contain exactly $2n$ points on both sides. Call this line $\ell_1$ .

Now, color the points on the left side of $\ell_1$ blue and the points on the right side of the line red. Let $P_0$ be a point of minimal distance to $\ell_1$ . Then slightly rotate $\ell_1$ so that no points other than $P_0$ lie on the line or switch sides, and $P_0$ lies through the rotated line. Consider the following windmill process. First, rotate $P_0$ clockwise until it passes through another point of different color, $P_1$ . Then for the $i$ th iteration of the process, when $\ell_1$ is $\overline{P_iP_{i+1}}$ , rotate it clockwise until it hits a new point $P_{i+2}$ with color different from $P_{i+1}$ , and then rotate $\ell_1$ about $P_{i+1}$ so that it becomes $\overline{P_{i+1}P_{i+2}}$ . Eventually, we can get the line to be in a position in which it passes through a red point and a blue point, dividing the plane into quadrants with $(n-1, n, n-1, n)$ points in them. Let this line intersect the original $\ell_1$ at point $X$ . Then rotate the line by a sufficiently small angular displacement about $X$ so that it passes through no point in $S$ . Call the resulting line $\ell_2$ . Then $\ell_1$ and $\ell_2$ divide the plane into quadrants with $n$ points in each quadrant, as claimed
:yoda:

:yoda:

Consider the two lines as in the above claim, and let their intersection be $X$ . Color the points in each quarter-plane red, blue, green, and yellow, in the clockwise order. I claim that the size $|T|$ of the set $T$ of triangles with all vertices of distinct colors containing the point $X$ in their interior is exactly $2n^3$ . Let $Q$ be the set of quadrilaterals with all vertices having distinct colors. Then for each quadrilateral $q \in Q$ , draw its diagonals and consider the $4$ subtriangles it is split into. Since $X$ lies in exactly one of those triangles, there are exactly $2$ triangles whose vertices are a subset of those of $Q$ that contain $X$ in its interior. Thus, $n|T|=2|Q|=2n^4$ , so $|T|=2n^3$ as desired.

Z K Y

The post below has been deleted. Click to close.

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

awesomeming327.

1735 posts

awesomeming327.

#7 h Feb 23, 2025, 12:37 AM

Y by

Another way to think about the problem after finding the first balancing line (assumed to be y=0) is to take a variable shear causing the median of the x-values on either side of the line to shift towards each other continuous, until we have n points in each quadrant.

Since isometries and shears are affine transforms, which preserve area ratios, the statement “X lies in ABC” is preserved, so we can make any translation, rotation, or shear to the original configuration that we want.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a