Given $ n$ points on the plane, which are the vertices of a convex polygon, $ n > 3$. There exists $ k$ regular triangles with the side equal to $ 1$ and the vertices at the given points. Prove that $ k < \frac {2}{3}n$. Construct the configuration with $ k > 0.666n$.
Problem
Source: I.F.Sharygin contest 2009 - Correspondence round - Problem 9
Tags: rotation, inequalities, geometry proposed, geometry
22.06.2009 15:50
Take any segment of length $ 1$ joining two points. It clearly cannot belong to more than $ 2$ of the $ k$ triangles. Moreover, if it belongs to $ 2$ of the triangles, no other of the $ 4$ vertices ($ 2$ common, $ 2$ different) may belong to any other triangle, since then a not strictly convex polygon would be formed by $ 5$ of the points (one regular triangle with two regular triangles "glued" to two of its sides). We may therefore divide the $ k$ triangles in $ u$ subsets of $ 1$ triangle and $ v$ subsets of $ 2$ triangles, such that $ 2$ triangles are in the same subset iff they share one side. Note also that each two distinct subsets may share at most one point, since otherwise they would share at least one side, or they would be the same subset. Since a set of $ 2$ triangles has $ 4$ points and a set of $ 1$ triangle has $ 3$ points, the total number of points is then $ n\leq3u+2v+1$, where $ 2u+v=k$, and equality is reached iff every two sets share exactly one point. Assume now that $ k\geq\frac{2n}{3}$, hence $ 6u+3v\geq6u+4v+2$, or $ v+2\leq0$, absurd. The conclusion follows. Consider now two equilateral triangles with sidelength $ 1$ sharing one side. Choose one of the vertices of the shared side and rotate the figure by angles $ \alpha,2\alpha,3\alpha,...,N\alpha$, with $ \alpha\leq\frac{\pi}{10^6N}$. The $ n=3N+1$ resulting points clearly form a convex polygon, and $ k=2N$ regular triangles with side $ 1$ arise in the figure, or it suffices to take $ N$ such that $ \frac{k}{n}=\frac{2N}{3N+1}>0.666=\frac{2}{3}-\frac{2}{3000}$, ie, $ N>333$.
13.08.2009 16:41
I think you mean $ n \ge 3u + 2v + 1$ because the arrangement you describe (sharing one point) produces the minimum number of points. The bounds are $ 4u + 3y \ge n \ge 3u + 2v + 1$. Then assuming $ k \ge \frac{2n}{3}$, you obtain: $ 2u + v \ge \frac{2n}{3} = \frac{2}{3}n \Rightarrow 6u + 3v \ge 2n$ Then, $ n \ge 3u + 2v + 1 \Rightarrow 2n \ge 6u + 4v + 2$ so $ 6u + 3v \ge 2n \ge 6u + 4v + 2 \Rightarrow 6u + 3v \ge 6u + 4v + 2 \Rightarrow 0 \ge v + 2$, which is the same contradiction you had reached.
13.08.2009 17:59
Aryth wrote: I think you mean $ n \ge 3u + 2v + 1$. You're absolutely correct, of course, my bad... The rest of my solution is OK though, I guess, and I actually wrote the wrong sign for the inequality, but used it immediately with the right sign