41 points are chosen in the unit square, no three in a line. Prove that some three make a triangle with area 0.1 or less

Question

I don't understand even where to begin. I know that the area of a triangle is the 1/2(height)(base). Please help!

Answer 1

Hi Sarah,

 

Indeed, this problem looks quite tricky at first.  However, if we carefully inspect what we know, maybe we can find a solution.  

 

Let's first name the points P₁, P₂, ... , P₄₁, in such a way that the x-coordinates are in ascending order, x₁ ≤ x₂ ≤ ... x₄₁.  Now, if we look through the set of x-coordinates for all triples which are closest together, we might be able to find some bound on the area of the triangles formed by the corresponding three points.

 

So, to start, let's let X = {x_i | 1≤i≤41} be the set of all x-coordinates, and define a second set T = {(x_i,x_i+1,x_i+2) | 1≤i≤39 and x_i,x_i+1,x_i+2 ∈ X}, and denote by t_i the element (x_i,x_i+1,x_i+2) in T.

 

Define the length of t_i by L(t_i) = x_i+2 - x_i.  Note that L(t_i) > 0, since no three x-coordinates of points can be equal, or else we would violate the condition of non-collinearity of any three points.  (All of this notation and definition is not completely necessary, by the way, but it makes it easier to refer to objects.)

 

The point now is to ask if there is necessarily some t_i whose length is "small"; or, put another way, can we find an upper bound for the minimum length of t_i's such that the triangle formed from the corresponding three points has an area no more than 0.1.

 

First, note that the minimum length can be as small as possible in general, since at worst two consecutive x-coordinates can be equal, and so the third one must necessarily be different---but it can be as close to the other two as we like.  But we want to prove that no matter what the distribution of the points in the unit square is like, there is a triangle of area no more than 0.1.   

 

So, let's conceive of the worst-case scenario---the one where the minimal distance is maximal.  This can happen if the x-coordinates are equal in pairs, with one lone x-coordinate somewhere.  Picture something like this, in the x-dimension:

 

: : : : : : : : : : : : : : . : : : : : :

 

In such a case, where the pairs and solitary lone x-coordinate are equi-distant from one another, we achieve the maximal minimum length of t_i's.

 

And now the major stroke of the pen (or flourish of the keys) is to compute what this separation between the points can be maximally.  Well, there are in this case 21 different x-coordinates, and therefore 20 equal gaps between them.  If we place the smallest x-coordinate(s) at x=0, and the last at x=1, then the gap-length is 1/20, which is therefore the maximal minimum length of any t_i.  

 

But now picture any three points P_i, P_i+1, P_i+2 whose x-coordinates are separated by a total of 1/20 and ask what an upper bound for the area of the triangle formed by them can be.  Well, the triangle must be contained in a rectangle of width 1/20 and height 1 (drawing a picture here helps), so its area must be less than the area of this rectangle, namely

 

A= (1/20)(1) = 0.05.

 

So we've actually attained a much better bound on the area of the triangle!

 

Hope this is not too hard to follow.

 

Regards,

Hassan