We are given $3n$ points $A_1,A_2, \ldots , A_{3n}$ in the plane, no three of them collinear. Prove that one can construct $n$ disjoint triangles with vertices at the points $A_i.$
Problem
Source:
Tags: geometry, combinatorial geometry, combinatorics, point set, Triangle, IMO Shortlist
nayel
26.06.2007 16:36
this is quite obvious actually. but for a formal proof you can use induction.
base case is trivial. assume it is possible for any such set of $3n$ points on the plane, for some $n$. now we need to prove it for the set $S$ of $3n+3$ such points. for that choose two of the points $A$ and $B$ such that all other points of $S$ lie on one side of the line $AB$. this is possible because no three points of $S$ are collinear. now choose a third point $C$ such that the triangle $ABC$ contains no other point of $S$. by our assumption the set $S-\{A,B,C\}$ can be divided into $n$ disjoint triangles. so $S$ itself can be divided into $n+1$ disjoint triangles, namely the $n$ triangles and $\triangle ABC$ .
paladin8
27.06.2007 05:55
I don't think that way of choosing point $C$ always works... o A o o C o o o B For example, while that is clearly the nonoptimal point $C$ it satisfies your condition yet fails the induction because the remaining three points will intersect $ABC$. I think a better choice would be to choose $C$ to be the point closest to line $AB$ so that any intersections would contradict this requirement.
digger
27.06.2007 10:36
nayel wrote: induction
Choose AB as presented and consider lines which go through the other 3n+1 points parallel to AB.
Take the nearest line L to AB. It contains one or two points. In any case we are done by induction because triangle is convex and
1) if L contains one point, say C, then we have triangle ABC and semiplane (excluding L themself) containing 3n points.
2) if L contains 2 points C and D then we have tiangle ABC again and semiplane (including L) which contains 3n points.
Altheman
29.06.2007 09:01
Proceed with induction on $n$. Base: $n=1$ Trivial...one triangle...it does not overlap. Induction step; assume that the statement is true for $n=k$ Consider the statement for $n=k+1$. Take an arbitrary line that passes through a point on the convex hull of the points and only passes through the convex hull at one point [it is at a "corner"]. Denote a side of the line with a little arrow. Let $f$ denote the points to the right of the line. Rotate $180$ degrees. $f$ changed from $0$ to $3(k+1)-1$ [or vice versa]. Since no 3 points are collinear, this function goes up by 1's. Hence $f$ is equal to $2$ at some point. Hence we can cut off those $3$ points. Induction hypothesis finishes the problem because none of the other triangles can overlap with the triangle that we removed since they are divided by the line.
Takeya.O
21.08.2016 19:04
We consider the straight line $L$ which isn't parallel to any $A_{i}A_{j}$.$L$ starts from the position of which all the points lie on one side,and moves parallel to the points.While moving,$L$ meets each point one by one.We suppose that $L$ meets the points in turns $p_1,\dots ,p_{3n}$.Then $(p_{3k-2},p_{3k-1},p_{3k})(1\le k\le n)$ satisfy the condition.$\blacksquare$
Anigasan1328
18.07.2018 18:16
You could use graph theory to solve this Simply take a assume the 3n points are all vertices. We have to prove that out of any vertex Ai, we need to be able to construct n triangles sticking out of the point. We can see that each vertex has degree n .