Consider a set of $n$ points in plane. Prove that the number of isosceles triangles having their vertices among these $n$ points is $\mathcal O (n^{\frac{7}{3}})$. Find a configuration of $n$ points in plane such that the number of equilateral triangles with vertices among these $n$ points is $\Omega (n^2)$.
Problem
Source: Iran 3rd round 2012-Special Lesson exam-Part1-P2
Tags: combinatorics proposed, combinatorics
20.12.2012 06:45
For the first part (which is a classical result; this is almost exactly the standard proof): Consider any point $P$ among the $n$; we will bound above the number of isosceles triangles with $P$ as a base vertex. Three points $P, Q, R$ form an isosceles triangle with base $PQ$ iff $Q$ lies on the circle centered at $R$ passing through $P$. That is, for each $P$ we want to count the number of incidences of the other $n - 1$ points on the $n - 1$ circles centered at each of these points and going through $P$. Inverting about $P$, this is the same problem as the number of incidences of $n - 1$ points on $n - 1$ lines, which by Szemeredi-Trotter is $ \mathcal{O} (n^{\frac{4}{3}}) $. Then summing over all $n$ points, the number of isosceles triangles that can be formed from points in the set is $ \mathcal{O} (n^{\frac{7}{3}}) $. For the second part: Consider an equilateral lattice formed from $n = \frac{k(k + 1)}{2}$ points. Simply remark that choosing any two points in the upper half of the lattice will determine a third vertex and therefore an equilateral triangle with all its vertices in the set, and that any triangle can be counted at most $3$ times. It follows that there are $\Omega(_\frac{n}{4}C_2) = \Omega(n^2)$ equilateral triangles that can be formed from these points.