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 $\sqrt2$ and 2)if no strip of length less that $\sqrt2$ covers all the four points, then the points are vertices of a square of length $\sqrt2$
Problem
Source: Romanian TST 2018 Problem 3 Day 2
Tags: combinatorial geometry, combinatorics
estetasks
28.10.2021 16:23
BUMP! Any solution?
x3yukari
02.11.2021 05:33
Beautiful !
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 touches two vertices of the triangle, WLOG let them be $A$ and $B.$ Let $A$ touch edge $e_a$ of the strip and $B$ touch edge $e_b$ of the strip. Now consider the foot of the altitude from $B$ to $e_a;$ let this be $Y.$ We can WLOG assume $C$ is on the same side of $AB$ as $Y$ (otherwise we rotate the figure $180^{\circ}$ and reassign $A, B,$ and $Y.$) We wish to minimize $BY,$ so since $BYA$ is a right triangle, and $BA$ remains fixed, it suffices to minimize $\angle BAY.$ Clearly this occurs when $ACY$ are collinear, since $\angle BAY \not<\angle BAC:$ otherwise $C$ would lie outside the strip. It follows that $BY$ is the height of $ABC.$ 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.
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 $\sqrt{2}.$
Claim (II): 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 $\sqrt{2}.$
Proof: 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 $\sqrt{2}.$
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 $\sqrt{2}.$ Since there exists a height of each triangle not greater than $1,$ this implies that for each triangle that has a height exceeding $\sqrt{2},$ there exists one side of that triangle that is greater than $\sqrt{2}$ times another side.
Extend pairs of opposite sides that they intersect. WLOG label the intersections $P, Q$ and the vertices of the quadrilateral $A, B, C, D$ such that $A$ lies collinear to and between $D, Q;$
$B$ lies collinear to and between $C, Q;$
$D$ lies collinear to and between $C, P;$
$A$ also lies collinear to and between $B, P;$
Consider side $DC.$ Since $A$ lies between $B$ and $P,$ the height from $B$ is clearly greater than the height from $A.$ Thus in triangle $BDC,$ one side is greater than $\sqrt{2}$ times $DC.$
Consider side $BC.$ Since $A$ lies between $D$ and $Q,$ the height from $D$ is clearly greater than the height from $A.$ Thus in triangle $BDC,$ one side is greater than $\sqrt{2}$ times $BC.$
From these two conditions, we obtain that $BD>\sqrt{2}BC$ and $BD>\sqrt{2}CD.$
Consider side $AB.$ Since $D$ lies between $C$ and $P,$ the height from $C$ is clearly greater than the height from $D.$ Thus in triangle $ABC,$ one side is greater than $\sqrt{2}$ times $AB.$
Consider side $AD.$ Since $B$ lies between $C$ and $Q,$ the height from $C$ is clearly greater than the height from $B.$ Thus in triangle $ADC,$ one side is greater than $\sqrt{2}$ times $AD.$
From these two conditions, we have four distinct cases to consider:
Case 1: $AC>\sqrt{2}AB, AC>\sqrt{2}AD.$
Using $BD>\sqrt{2}BC, AC \cdot BD > 2AD \cdot BC.$
Using $BD>\sqrt{2}CD, AC \cdot BD > 2AB \cdot CD.$
Summing both inequalities and dividing by two, $AC \cdot BD > AD \cdot BC + AB \cdot CD,$ which contradicts Ptolemy's Inequality
Case 2: $AC>\sqrt{2}AB, CD>\sqrt{2}AD.$
We consider the following two sub-cases:
Sub-case 1: $CD \geq BC.$ Now using $BD>\sqrt{2}CD$ and $AC>\sqrt{2}AB, AC \cdot BD > 2AB \cdot CD > AB \cdot CD + AD \cdot BC,$ using $CD>BC.$ This contradicts Ptolemy's inequality
Sub-case 2: $BC>CD.$ Now using $BD>\sqrt{2}BC$ and $AC>\sqrt{2}AB, AC \cdot BD > 2AB \cdot BC.$ Since $BC>CD,$ it remains to prove $AB>AD=\frac{\sqrt{2}}{2}CD.$ But suppose the contrary; then $AD+AB<2\cdot\sqrt{2}{2}CD<\sqrt{2}BC$ which contradicts the Triangle Inequality. It follows that $AC \cdot BD > 2AB \cdot BC > AB \cdot CD + BC \cdot AD.$ But again this contradicts Ptolemy's Inequality. Likewise, Case 3 ($BC>\sqrt{2}AB, AC>\sqrt{2}AD$) is similar to Case $2.$
Case 4: $BC>\sqrt{2}AB, CD>\sqrt{2}AD.$
Using $BD>\sqrt{2}BC, BD>2AB$
Using $BD>\sqrt{2}CD, BD>2AD$
Summing both inequalities and dividing by two, $BD>AB+AD,$ a contradiction by Triangle Inequality.
Note that cases where $ABCD$ 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 $\sqrt{2}.$)
Thus there exists a side that has both of the heights from the other two points not greater than $\sqrt{2}.$ It follows that there exists a strip of length at most $\sqrt{2}$ covering the entire quadrilateral. Q.E.D.
Part II is simple now; from the proof by contradiction change all strict inequalities to non-strict inequalities. The only equality case clearly occurs when $AB=BC=CD=DA$ and $AC=BD=\sqrt{2}AB,$ and since Ptolemy's inequality is non-strict as well, this does not yield a contradiction. This yields a square with length $\sqrt{2},$ and since that figure clearly works, if no strip of width less than $\sqrt{2}$ covers all four points, the points are vertices of a square of length $\sqrt{2}.$
...