Tuesday, November 20, 2007

klien's problem

I found this problem asing to be attacked by PHP, later I learnt this was generalized by Erdos and Szekeres(happy ending problem).

Let there be 5 points arbitrarily lying on a plane.Prove that we can find four points that form a convex quadrilateral.

classic proof: If the smallest convex polygon encompassing all the points is quadrilateral or pentagon, then we are done. Else, if it is a triangle (say ABC) and D and E are interior points.Among three points A, B, C two points lie on one side of DE and we are done.
Another proof:(I feel this is not elegant as the previous one)

Let three points A,B,C form a triangle.Now I think how I can introduce the 4th point.Reffering to pic1 if I introduce the 4th point in the non red regions we are done. So let me proceed by putting 4th point in red region. This results in pic2 that is equivalent to introducing the 4th point within triangle ABC.
If the 5th point is introduced outside triangle ABC we are done.Else if introduced within ABC we get a convex quadrilateral involving D.

No comments: