Consider a 4-point configuration in the plane such that every 3 points can be covered by a strip of a unit width. Prove that:
1) the four points can be covered by a strip of length at most and
2)if no strip of length less that covers all the four points, then the points are vertices of a square of length
Solution
1. Claim (I): For the triangle formed by each triple of points, there exists a height of that triangle not greater than 1.
Proof:
Consider the smallest possible strip covering three points at a given angle. Clearly, this strip touches two vertices of the triangle, WLOG let them be and . Let touch edge of the strip and touch edge of the strip. Now consider the foot of the altitude from to ; let this be . We can WLOG assume is on the same side of as (otherwise we rotate the figure and reassign and ). We wish to minimize , so since is a right triangle, and remains fixed, it suffices to minimize . Clearly, this occurs when are collinear, since ; otherwise would lie outside the strip. It follows that is the height of . Proceeding similarly with all possible pairs of points on the edges of the strips, and orientations of the third point, it follows that the least possible width of the strip is the least possible height of the triangle, which is not greater than 1 by the condition.
2. **Claim (II): The four points can be covered by a strip of width at most .
Proof:**
We wish to prove the quadrilateral formed by 4 points, which triple-wise have the least height of the triangle formed by them not greater than 1, fits into a strip of width . This is equivalent to the assertion that there exists a side for which the heights of the two triangles formed by them are both not greater than .
Proceeding similarly as with Claim (I), we find that the minimum possible width of the strip covering a triangle with the boundary going through two vertices on opposite sides occurs when one side is collinear with the boundary of the strip. It follows that the minimum possible width of the strip covering the entire quadrilateral occurs when the triangle formed by three points is completely covered, with one side collinear with one boundary and the remaining point on the opposite boundary; and with the fourth point not outside the strip. Thus the minimum possible width of the strip occurs when the maximum height of the two triangles formed by a given side and one of the two remaining points is minimized. We wish to prove that this does not exceed .
We proceed with a proof by contradiction. Suppose that for each side of the quadrilateral, there exists a point such that the height from that point to the side of the quadrilateral exceeds . Since there exists a height of each triangle not greater than 1, this implies that for each triangle that has a height exceeding , there exists one side of that triangle that is greater than times another side.
Extend pairs of opposite sides so that they intersect. WLOG label the intersections and the vertices of the quadrilateral such that lies collinear to and between ; lies collinear to and between ; lies collinear to and between ; also lies collinear to and between . Consider side . Since lies between and , the height from is clearly greater than the height from . Thus in triangle , one side is greater than times . Consider side . Since lies between and , the height from is clearly greater than the height from . Thus in triangle , one side is greater than times . From these two conditions, we obtain that and . Consider side . Since lies between and , the height from is clearly greater than the height from . Thus in triangle , one side is greater than times . Consider side . Since lies between and , the height from is clearly greater than the height from . Thus in triangle , one side is greater than times . From these two conditions, we have four distinct cases to consider:
- Case 1: . Using . Using . Summing both inequalities and dividing by two, , which contradicts Ptolemy's Inequality.
- Case 2: . We consider the following two sub-cases:
- Sub-case 1: . Now using and , using . This contradicts Ptolemy's inequality.
- Sub-case 2: . Now using and . Since , it remains to prove . But suppose the contrary; then which contradicts the Triangle Inequality. It follows that . But again this contradicts Ptolemy's Inequality.
- Case 3: is similar to Case 2.
- Case 4: . Using . Using . Summing both inequalities and dividing by two, , a contradiction by Triangle Inequality.
Note that cases where is a trapezoid/rectangle can be proved similarly (except some steps may be omitted since for two sides we have the added restriction that both heights must exceed ).
Thus there exists a side that has both of the heights from the other two points not greater than . It follows that there exists a strip of length at most covering the entire quadrilateral. Q.E.D.
3. **Part II: If no strip of length less than covers all the four points, then the points are vertices of a square of length .
Proof:**
From the proof by contradiction, change all strict inequalities to non-strict inequalities. The only equality case clearly occurs when and , and since Ptolemy's inequality is non-strict as well, this does not yield a contradiction. This yields a square with side length , and since that figure clearly works, if no strip of width less than covers all four points, the points are vertices of a square of side length .