Let $P_1,P_2,...,P_{2556}$ be distinct points inside a regular hexagon $ABCDEF$ of side $1$. If any three points from the set $S=\{A,B,C,D,E,F,P_1,P_2...,P_{2556}\}$ aren't collinear, prove that there exists a triangle with area smaller than $\frac{1}{1700}$, with vertices from the set $S$.
Problem
Source: Kosovo TST 2015 Q4
Tags: combinatorics, pigeonhole principle
mavropnevma
30.03.2015 18:22
Any triangulation of the hexagon, using its $6$ vertices and the $2556$ interior points is made of $(6-2) + 2\cdot 2556 = 5116$ triangles. The area of the hexagon is $\dfrac {3\sqrt{3}}{2}$, therefore one of the triangles has area at most $\dfrac {3\sqrt{3}}{2\cdot 5116} < \dfrac {1}{1969} < \dfrac {1}{1700}$. Quite a better bound.
RadioActive
31.03.2015 00:55
Can we use expected value here? I have that the expected number of points in any given triangle that has an area of $\frac{1}{1700}$ is $2556 \times \frac{1}{1700} \div \frac{3 \sqrt{3}}{2} \approx 3.9$. This means that there must be one triangle in which there are at least 4 points inside the triangle. Pick any 3 points and you can construct a triangle with an area less than $\frac{1}{1700}$.
User335559
26.03.2017 16:25
mavropnevma wrote: Any triangulation of the hexagon, using its $6$ vertices and the $2556$ interior points is made of $(6-2) + 2\cdot 2556 = 5116$ triangles. The area of the hexagon is $\dfrac {3\sqrt{3}}{2}$, therefore one of the triangles has area at most $\dfrac {3\sqrt{3}}{2\cdot 5116} < \dfrac {1}{1969} < \dfrac {1}{1700}$. Quite a better bound. Where did you get that $(6-2) + 2\cdot 2556 = 5116$?