Suppose there are $n$ points in a plane no three of which are collinear with the property that if we label these points as $A_1,A_2,\ldots,A_n$ in any way whatsoever, the broken line $A_1A_2\ldots A_n$ does not intersect itself. Find the maximum value of $n$. Dinu Serbanescu, Romania
Problem
Source: JBMO 2003, Problem 2
Tags:
12.10.2005 07:27
The first four points must form a concave quadrilateral (otherwise the diagonals intersect), and considering the possible places to put the fifth point, the broken line can always intersect itself. So $n=4$
12.01.2006 20:19
Consider the figeure fromed by the n points as a graph and the broken line as a tree in that graph. I will prove that the shortest tree in that graph has the requested property: If two edges of the tree: $AB$ intersects $CD$ then the line obtained by eliminating $AB$ and $CD$ from the tree and inserting edges $AC$ and $BD$ will be shorter. (by triangle ineq) so we are done.
13.01.2006 00:17
It is easy to see that if $4$ of the points are the vertices of a convex quadrilateral then the desired property is not satisfied. Moreover, it is well-known that among any set of $5$ points in the plane, no three being colinear, we may find $4$ which are the vertices of a convex quadrilateral (this is the famous Esther Klein-Szekeres' result). Thus the maximum number of points is at most $4$. In another hand, considering the three vertices of an equilateral triangle and its center, wa have a 'good' configuration with $4$ points. Pierre.
26.06.2009 16:38
First we can say that, if we choose 5 points in plane with no three are collinear, there is a such 4 points this points are vertices of a convex quadrilateral. and in quadrangle diognals are intersect so that n=4 is maximal. If we choose 4 points such that this points are vertices of a concave quadrilateral, this is ok.