n points are given on a plane where n≥4. All pairs of points are connected with a segment. Find the maximal number of segments which don't intersect with any other segments in their interior.
Problem
Source: Turkey National Olympiad P3
Tags: combinatorics, combinatorics proposed
25.07.2016 20:46
Any answer or idea?
27.07.2016 01:33
Let's consider an arbitrary arrangement of n points and adding a new point in there. We'll consider few cases. Consider the convex hull of the n points and first let's add the new point outside of that convex hull. If the new convex hull has the same amount of points on the boundary as the previous one, it's essentially the same as adding the point inside of the convex hull (just consider swapping the one point that was on the boundary in the first convex hull, but inside of the second with the new point we're adding). So now we just check when the convex hull has one more point on the boundary. Since in every convex polygon every diagonal is intersected at least once by another diagonal, by adding a new point like we described we can increase the number of nonintersecting segments by at most 2 (actually we will lose at least one of the nonintersecting segments from the previous configuration, but this claim will do it). Now let's consider adding the new point inside of the convex hull of the initial n points. First denote the intersections of some segments, if any with some points and it's easy to notice that the convex hull is "triangualted" (some triangles may overlap). So whenever we add the new point inside it will be inside of some triangle (the case when we add a new point on an already existing edge is easily discarded). Consider the smallest triangle that contains the new point and no other point inside (or the boundaries), including the intersection points. If the 3 vertices of the triangle are all from the initial n points then the sides of that triangle are non-intersecting segments, as every intesected edge has a point on it, which contradicts the fact that the triangle is the smallest one. Then we can increase the number of non-intersecting edges by at most 2 (we add 3 new edges by connecting the new point to the vertices, all other edges adjacent to the new point are intersected, but additionally at least one of the sides of the triangle is intersected). If at least one of the vertices is an intersection point, we can increase the number of non-intersecting edges by at most 2 (we add at most 2 non-intersecting edges, although none of the previously non-intersected edges might be intersected). So from all this we can conclude that by adding a new point the number of non-intersecting edges can be increase by at most 2. Hence the maximum number of edges for n points is: 6+2(n−4)=2n−2, as for n=4 the maximum number is 6. Now we'll give a construction of n points and 2n−2 non-intersecting. edges. Consider a semicircle with diameter A2A3. Now let the points A4,A5,...,An lie on that semicircle. Now let A1 lie on the bisector of A2A3. As A1 goes further and further away from the semicircle eventually all the points will lie inside the triangle A1A2A3. Obviously the n−1 sides of the (n−1)-agon A2A3,...,An and the n−1 segments connecting A1 with any other point are the 2n−2 non-intersecting edges.