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.
Problem
Source: JBMO 2007, Bulgaria, problem 3
Tags: combinatorics proposed, combinatorics, combinatorial geometry, Hi
28.06.2007 22:50
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.
20.01.2017 12:20
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}$ " ??
18.03.2023 03:46
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.
10.08.2023 00:05
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.
15.10.2023 00:52
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$
09.12.2023 18:09
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$.
04.01.2024 22:18
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.
01.05.2024 07:59
smol
01.05.2024 08:11
13.08.2024 14:13
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
11.09.2024 11:19
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.