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 60503=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 60503=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 ⌊60503⌋=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 ⌊n3⌋. 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.