Let us have $6050$ points in the plane, no three collinear. Find the maximum number $k$ of non-overlapping triangles without common vertices in this plane.
Problem
Source: Moldova TST for EGMO 2017, prob. 3
Tags: combinatorics
26.04.2017 15:33
I'm sorry, but I might not understand. Doesn't the fact that no $2$ triangles have a common vertex mean that a point can be vertex in only one triangle, so there can be at most $\frac{6050}{3}=2016$ triangles?
26.04.2017 20:44
andrei.pantea wrote: I'm sorry, but I might not understand. Doesn't the fact that no $2$ triangles have a common vertex mean that a point can be vertex in only one triangle, so there can be at most $\frac{6050}{3}=2016$ triangles? Yes you got it right. The answer is correct but you have to show how you can make 2016 triangles with the given conditions
26.04.2017 21:53
There are at most $\left \lfloor \frac{6050}{3} \right\rfloor=2016$. We will prove that it is the desired number. Let call the points $1,2,3,...,6050$. A set of $2016$ triangles whose vertices are $1,2,...,6050$ is said to be relatively good if no triangles share a vertex. Such a set exists since the set of triangles formed by joining $(1,2,3)$, $(4,5,6)$, $(7,8,9)$,....,$(6046,6047,6048)$ is a relatively good set. Let $T$ be a relatively good set with the minimal area of overlapping between its triangles. We will prove that in fact the triangles of $T$ don't overlap. Assume two triangles, W.L.O.G $(1,2,3)$ and $(4,5,6)$, overlap. Case 1: The line $(4,5)$ doesn't intersect the triangle $(1,2,3)$. The closest point in the triangle $(1,2,3)$ to the segment $(4,5)$ is one of its vertex. W.L.O.G $1$. replace the triangles $(1,2,3)$ and $(4,5,6)$ by $(1,4,5)$ and $(2,3,6)$, these triangles don't overlap since $1$ is the unique farthest point in the triangle $(1,4,5)$ from the segment $(4,5)$. which contradicts the choice of $T$. Case 2: The line $(4,5)$ intersects the triangle $(1,2,3)$. In this case the line separates the vertices of the triangle into two sets, one of them contains exactly one point and the other two points. Assume $(4,5)$ is horizontal and the lowest edge of the triangle $(4,5,6)$. If there is only one point below $(4,5)$, say $1$, then consider $(1,4,5)$ and $(2,3,6)$ and they don't intersect since we can separate them by taking a line parallel to $(4,5)$ which lies between $(4,5)$ and the points $2,3,6$ . If there are two points below $(4,5)$, say $1$ and $2$, then consider $(1,2,4)$ and $(5,3,6)$ one of them is ( almost ) above the line $(4,5)$ and the other is below.
26.04.2017 23:57
siddigss wrote: Assume two triangles, W.L.O.G $(1,2,3)$ and $(4,5,6)$, overlap. The closest point in the triangle $(1,2,3)$ to the segment $(4,5)$ is one of its vertex. W.L.O.G $1$. replace the triangles $(1,2,3)$ and $(4,5,6)$ by $(1,4,5)$ and $(2,3,6)$, these triangles don't overlap since $1$ is the unique farthest point in the triangle $(1,4,5)$ from the segment $(4,5)$. which contradicts the choice of $T$. I think I might have found a counter-example, could you please clarify
Attachments:

27.04.2017 00:30
Yes, you are right ! what I wrote works if the line $(4,5)$ doesn't intersect $(1,2,3)$. The remaining case - which is your example - is if the line $(4,5)$ intersects the triangle $(1,2,3)$ in which case the line separate the vertices of the triangle into two sets, one of them contains exactly one point and the other two points. Assume $(4,5)$ is horizontal and the lowest edge of the triangle $(4,5,6)$. If there is only one point below $(4,5)$, say $1$, then consider $(1,4,5)$ and $(2,3,6)$ and they don't intersect since we can separate them by taking a line parallel to $(4,5)$ which lies between $(4,5)$ and the points $2,3,6$ . If there are two points below $(4,5)$, say $1$ and $2$, then consider $(1,2,4)$ and $(5,3,6)$ one of them is ( almost ) above the line $(4,5)$ and the other is below.
27.04.2017 01:50
It remain to prove that if we have $n$ points no three of them collinear we can form $\lfloor \frac{n}{3}\rfloor$. it suffices to draw parallel lines through all the points .there is at most 2 points then you can begin by the line in the far border and use the points of the near nighbour lines successively.