Seeking Feedback on my solution: Maximum area of a triangle inside a rectangle.

250 Views Asked by At

I was solving problem 3.3.16 from Paul Zeitz's book "The Art and Craft of Problem Solving." The problem reads

Inside a 1 x 1 square, 101 points are placed.Show that some three of them form a triangle with area no more than 0.01.

This is a straightforward application of pigeonhole principle. If we divide the square into 50 rectangles of size 2/10 x 1/10, then three will lie in one of the rectangles. So the maximum are of such a triangle is 1/2 x 2/10 x 1/10 which is 0.01. But the loose end to the solution is the assumption that if there are three points in one rectangle, the area of the triangle can be atmost 1/2 of that of the rectangle. The argument has to be made more rigorous.

So I thought of the following. Let PQRS be the rectangle. Let ABC be the triangle. Pick any side of the triangle, say AB. Produce it to meet the rectangle at D and E. Then

  1. area of DEC is greater than that of ABC since DE > (or equal to) AB.

Next, I draw a line 'l' parallel to AB and passing through C. Any other point on 'l' (say X) is such that area of DEX is same as area of ABC. If I move l parallel to AB, then

  1. height from X to AB is maximum when 'l' passes through the vertex which is farthest from AB (basically we can drop perpendiculars from all the vertices of PQRS on to AB to decide which one is farthest).

Choose X to be that vertex (say P). Then DEP forms the upper bound to the area of such a triangle. So now, we have

  1. area(ABC) < area(DEC) < area(DEP).

Beyond this point, I need some hint to arrive at the solution. Please give me some ideas which I can use to proceed.

EDIT1: I could go further. I am writing it down here and I would appreciate it if you can please let me know whether I am right and if not, please show me where I am going wrong.

  1. The point D or E has to lie on sides of PQRS. Specifically, PD or PE (one of the two) lie along a side of PQRS which contains P.

Let PE be the side of DEP that lies along PS, a side of PQRS. Then

  1. area(DEP) < area(DSP).

But area(DSP) = area(QSP) = 1/2 x area(PQRS). Hence, from the chain of inequalities that we obtained above in an attempt to bound the area(ABC), we get

  1. area(ABC) < 1/2 x area(PQRS).

EDIT2:

I figured that there is an error in point #4 above. Specifically, I mentioned that "Specifically, PD or PE (one of the two) lie along a side of PQRS which contains P." That is true ONLY if D and E lie on opposite sides of PQRS.

If D and E lie on adjacent sides of PQRS, situation is different. Let D lie on QR and E on QP. Let the altitude from S be the largest as compared to the ones from R, P or Q. It is easier to handle the case when the altitude from P, R or Q is the longest since in that case, atleast one of the DEX (X=P, R or Q) lie along the side of PQRS and that case is argued before. In case the longest altitude to DE is from S, then I could think of the following.

  1. Draw line 'm' parallel to DS and through E. Then choose that vertex of PQRS that has the longest altitude to 'm' (say P) so that area(DES) < area(DPS) = 1/2 x area(PQRS). Then we can conclude that area(ABC) < 1/2 x area(PQRS).

I just want to make the argument as (logically) error free as possible with no loose ends in the chain of logic. I would greatly appreciate it if you can please provide feedback.