50 points in 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

No tags match your search

M

50 points in plane

G H J

Reveal topic tags

combinatorics proposed

combinatorial geometry

L

G H BBookmark kLocked kLocked NReply

Source: JBMO 2007, Bulgaria, problem 3

The post below has been deleted. Click to close.

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

1145 posts

#1 h Jun 28, 2007, 12:30 PM • 13 Y

Y by Adventure10, Mathlover_1, OronSH, aidan0626, Blue_banana4, PikaPika999, and 7 other users

Given are $50$ points in the plane, no three of them belonging to a same line. Each of these points is colored using one of four given colors. Prove that there is a color and at least $130$ scalene triangles with vertices of that color.

Z K Y

The post below has been deleted. Click to close.

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

267 posts

bodan

#2 h Jun 28, 2007, 7:50 PM • 24 Y

Y by amirmath1995, Catalanfury, Nguyenhuyhoang, silouan, raven_, DepressedCubic, Adventure10, Mathlover_1, Mango247, aidan0626, Blue_banana4, Funcshun840, PikaPika999, kiyoras_2001, and 10 other users

Lemma. Among $n$ points in a plane positioned generally (no three collinear) we have at least $\frac{n(n-1)(n-8)}{6}$ scalene triangles.
Proof. Suppose that $n$ points are fixed and the number of isosceles triangles is $\alpha$ . Set $\beta$ to be the number of bases of these triangles (we count three bases for each equilateral and one for each nonequilateral isosceles triangle). Clearly $\beta\geq \alpha$ . Then each segment connecting a pair of points can be a base of at most two triangles, as if this is not the case three points will lie on this pairs' perpendicular bisector. Thus there are at most $2{n\choose 2}$ isosceles triangles, yielding that there are at least ${n\choose 3}-2{n\choose 2}=\frac{n(n-1)(n-8)}{6}$ scalene triangles. $\square$

In the problem there are at least $13$ points of the same color and we apply the lemma.

Z K Y

The post below has been deleted. Click to close.

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

218 posts

#3 h Jan 20, 2017, 9:20 AM • 3 Y

Y by Adventure10, Mango247, PikaPika999

why the fact "there are at most $2{n\choose 2}$ isosceles triangles"
does not imply "#scalene triangle + #acute triangle(except isosceles and equilateral triangle) is at least ${n\choose 3}-2{n\choose 2}=\frac{n(n-1)(n-8)}{6}$ " ??

Z K Y

The post below has been deleted. Click to close.

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

1292 posts

#4 h Mar 18, 2023, 12:46 AM • 1 Y

Y by PikaPika999

bodan wrote:

Lemma. Among $n$ points in a plane positioned generally (no three collinear) we have at least $\frac{n(n-1)(n-8)}{6}$ scalene triangles.
Proof. Suppose that $n$ points are fixed and the number of isosceles triangles is $\alpha$ . Set $\beta$ to be the number of bases of these triangles (we count three bases for each equilateral and one for each nonequilateral isosceles triangle). Clearly $\beta\geq \alpha$ . Then each segment connecting a pair of points can be a base of at most two triangles, as if this is not the case three points will lie on this pairs' perpendicular bisector. Thus there are at most $2{n\choose 2}$ isosceles triangles, yielding that there are at least ${n\choose 3}-2{n\choose 2}=\frac{n(n-1)(n-8)}{6}$ scalene triangles. $\square$

In the problem there are at least $13$ points of the same color and we apply the lemma.

Thanks. I had almost the exact same solution, except one question. Why do you care about “ we count three bases for each equilateral and one for each nonequilateral isosceles triangle”? It seems that already 2 bases of triangles at most x n choose 2 pairs of points to form an isosceles triangle is enough.

Z K Y

The post below has been deleted. Click to close.

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

5608 posts

#5 h Aug 9, 2023, 9:05 PM • 2 Y

Y by OronSH, PikaPika999

We solve the following problem first:

Given are $13$ points in the plane, no three of them belonging to a same line. Prove that there are at least $130$ scalene triangles with vertices in the plane.

Notice that any edge between two points in the plane can be a base of at most two isosceles triangles (because otherwise we would have $3$ points on the perpendicular bisector). Hence there are at most $\binom{13}{2} \cdot 2 = 256$ isosceles triangles, so at lesat $\binom{13}{3} - 256 = 130$ scalene triangles.

This solves the original problem because there must exist a color with at least $\left\lceil \frac{50}{4} \right\rceil = 13$ points of that color.

This post has been edited 3 times. Last edited by megarnie, Aug 9, 2023, 9:11 PM

Z K Y

The post below has been deleted. Click to close.

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

7585 posts

#6 h Oct 14, 2023, 9:52 PM • 1 Y

Y by PikaPika999

We prove that given 13 points in standard position, there are 130 scalene triangles. This clearly solves the original question.

Note that every base (i.e. two points) gives at most two isosceles triangles, else we have three points along the perpendicular bisector.

Therefore there are at most $\binom{13}{2}\cdot 2=156$ isosceles triangles. At the same time there are $\binom{13}{3}=286$ triangles in total, making 130 non-isosceles AKA scalene triangles. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

1327 posts

#8 h Dec 9, 2023, 3:09 PM • 1 Y

Y by PikaPika999

By pigeonhole, there is a color that has at least $13$ points of the same color. This means there are $\binom{13}{3} = 286$ triangles that can be formed.
Let $I$ be the number of isosceles triangles in the $13$ points.
Then each pair of two points can contribute at most $2$ to $I$ (due to the collinear condition), so $\binom{13}{2} \cdot 2 = 156$ is the maximum number of isosceles triangles. Then the minimum number of scalene triangles is $130$ .

This post has been edited 1 time. Last edited by dolphinday, Dec 9, 2023, 3:09 PM

Z K Y

The post below has been deleted. Click to close.

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

652 posts

#9 h Jan 4, 2024, 7:18 PM • 1 Y

Y by PikaPika999

By Pigeonhole, some color has at least $13$ points of that color. So, assume there are exactly $13$ points, we'll show that we can find at least $130$ scalene triangles whose vertices all belong to those $13$ . First, the total number of triangles is $\binom{13}{3} = 286$ . Also, note that for each pair of points $(A, B)$ , there are at most two isosceles triangles $ABC$ which have $\overline{AB}$ as a base, since in order for that to happen, $C$ must lie on the perpendicular bisector of $\overline{AB}$ , but if three or more $C$ exist, this is a contradiction to the fact that no three points are collinear. So, there are at most $2 \cdot \binom{13}{2} = 156$ isosceles triangles, thus at least $130$ scalene triangles among those $13$ points (basically at least $130$ of that color), so done.

Z K Y

The post below has been deleted. Click to close.

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

280 posts

#10 h May 1, 2024, 4:59 AM • 1 Y

Y by PikaPika999

smol
solution

This post has been edited 1 time. Last edited by InterLoop, May 1, 2024, 5:00 AM

Z K Y

The post below has been deleted. Click to close.

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

4223 posts

#11 h May 1, 2024, 5:11 AM • 1 Y

Y by PikaPika999

https://cdn.aops.com/images/b/8/2/b824a1d2347b72751984bb68d01bd220d96d5d63.png

Z K Y

The post below has been deleted. Click to close.

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

60 posts

kotmhn

#12 h Aug 13, 2024, 11:13 AM • 1 Y

Y by PikaPika999

On each base at most 2 isosceles can lie else the collinearity condition is violated.
By PHP 13 dots of same color exist. then at most $2{13 \choose 2} = 156$ isosceles triangles and total triangles equal ${13 \choose 3}=286$ so at least $286-156=50$ triangles.
done

This post has been edited 1 time. Last edited by kotmhn, Aug 13, 2024, 11:14 AM
Reason: arithmetic skill issue

Z K Y

The post below has been deleted. Click to close.

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

235 posts

#13 h Sep 11, 2024, 8:19 AM • 1 Y

Y by PikaPika999

Start with a claim.

Claim: For any $x$ points in the plane (no three collinear), there are atleast $\binom{x}{3}-2\binom{x}2$ scalene triangles formed by it.
Proof: The maximum number of isosceles triangles by choosing a fixed base is atmost $2$ or else there will be $3$ points on the perpendicular bisector of the base. $\blacksquare$ .

And hence choose the colour with atleast $\left \lceil \frac{50}4 \right \rceil=13$ points and the number of scalene triangles it form are atleast $\binom{13}3-2\binom{13}2=130$ as desired.

This post has been edited 1 time. Last edited by ihategeo_1969, Sep 11, 2024, 8:20 AM

Z K Y

The post below has been deleted. Click to close.

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

201 posts

#14 h Apr 6, 2025, 9:38 PM • 1 Y

Y by PikaPika999

Note that by pigeonhole there exists a color that repeats at least $13$ times. Then, since there are no three points that are colinear, each line segment drawn in these $13$ points can be the base for at most $2$ isoceles triangles, thus there are at least $\binom{13}{3}-\binom{13}{2}2=130$ scalene triangles with same colored vertices.

Z K Y

The post below has been deleted. Click to close.

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

cursed_tangent1434

634 posts

cursed_tangent1434

#15 h May 6, 2025, 6:33 AM

Y by

Let $x$ denote the number of points of the color with the highest frequency. There are clearly $\binom{x}{3}$ triangles. For any line segment connecting any two of these points, at most 2 isosceles triangles with this segment as the base may be constructed since we are given that no three points are collinear as any vertex for which the resulting triangle is isosceles must lie on the perpendicular bisector of this segment. Hence we have atleast,
$S\ge \binom{x}{3} -2\binom{x}{2} = \frac{x(x-1)(x-2)}{6} - x(x-1) = \frac{x(x-1)(x-8)}{6}$ scalene triangles all of whose vertices are of this same color. However since we have 50 points and only 4 colors, there exists some color with atleast, $\lceil \frac{50}{4} \rceil = 13$ points of that color. But then,
$S \ge \frac{x(x-1)(x-8)}{6} \ge \frac{13\cdot 12 \cdot 5}{6} = 130$ scalene triangles with all vertices of the same color, as desired.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a