Vayutuvan wrote:Amber G., you might know about the "happy ending problem" which was described in the book on Erdos. Let me pose it here.
Given five points in general position in a plane, i.e. no three points form a straight line, prove that there is always a convex quadrilateral.
The problem was given to Erdos and Szekeris by their friend Esther Klien. Both the men scratched their heads until Esther gave the solution.
It was the start of Ramsey Theory program by Erdos and Szekeris.
Erdos gave the problem that name because Szekeris and Esther Klein started a romantic relationship which ended in their marriage.
I actually found this one rather easy, don't know if I made some major reasoning error (it's possible). I didn't look it up though, the below are my own thoughts on it.
Ee-e-nh, let's see now (as Bugs Bunny once said)....
Three non-collinear points in a plane will form a triangle, which is always considered convex. When you add a fourth point, which is not collinear with any any of the pairs of previous three points, the quadrilateral formed will be convex if each of the points are outside the triangle formed by the other three. Conversely, if the quadrilateral is concave, then one of the four points will be in the triangle formed by the other three (but not *on* the triangle, since the "no three collinear points" rule precludes that).
So of the five points, select any four. If these four form a convex quad, then the problem is over right there.
So we are concerned with the case where these four don't form a convex quad. Which means, one of them is inside the triangle formed by the other three.
So pick any triangle, and place a point inside it. It is to be shown that if we select a fifth point which is not collinear with any pair out of the previous four, then this fifth point will be such that, at least four out of the five will form a convex quad.
See the figure below. Three of the red dots form a triangle, and the fourth red dot is inside this triangle.
The fifth point cannot lie on any of the green or black lines. So the fifth point has to lie within one of the pink, grey, or blue regions.
