# A cute combinatorial result of Santaló

There is a nice result due to Santaló that says that if a (finite) collection of axis-parallel rectangles is such that any small subcollection is aligned, then the whole collection is aligned. This is kind of surprising at first, because the condition only says that there is a line, but this line might be different for any choice of subcollection. The precise statement is as follows:

Theorem. Let $\mathcal{R}$ be a collection of rectangles with sides parallel to the axes (possibly intersecting). If for every choice of 6 rectangles of $\mathcal{R}$ there exists a line intersecting all $6$ of them, then there exists a line intersecting all rectangles of $\mathcal{R}$ at once.

To be precise, I should clarify that by line intersection it is meant intersection with the interior of the rectangle – so a line touching only the boundary is not allowed. The number 6 doesn’t have any special esoteric meaning here, to the best of my understanding – it just makes the argument work.

The proof of this result is by induction on the number $N$ of rectangles. If $N = 6$ then the result trivially holds, so let $N+1 > 6$ and suppose the theorem is true for any collection $\mathcal{R}$ of $N$ rectangles satisfying the property that for every choice of $6$ rectangles of $\mathcal{R}$ there exists a line intersecting all $6$ of them.
We let $\mathcal{R} = \{R_1, R_2, \ldots, R_{N+1}\}$. For every rectangle $R_j$, by inductive hypothesis there exists a line $\ell_j$ that intersects every rectangle in the collection $\mathcal{R} \backslash \{R_j\}$. If one of these intersects $R_j$ itself then we are done, so we assume that each $\ell_j$ does not intersect $R_j$ (but it intersects every other rectangle; in particular, it intersects $N$ rectangles of $\mathcal{R}$). We will argue by a bit of convexity that there must be a line $\ell$ (in general distinct from the lines $\ell_j$) that crosses everyone of the $N+1$ rectangles at once.
We assume for simplicity that none of the lines $\ell_j$ are horizontal (if there are horizontal ones, just add a small perturbation to their slope). In this case we can write down the equation of each line as
$\ell_j : \qquad x + b_j y + c_j = 0.$
Select four distinct indices $j_1, j_2, j_3,j_4$ such that $b_{j_1}, b_{j_2}, b_{j_3},b_{j_4}$ all have the same sign (thus the corresponding lines are either all pointing upward or all pointing downward). Notice that you can do this because there are at least 7 lines – here is where that number $6$ in the statement comes from. The two cases are treated in the same way, so assume that the lines are all pointing downward – that is $b_{j_1}, b_{j_2}, b_{j_3},b_{j_4}$ are all positive. Now consider a non-trivial solution to the system of equations

\displaystyle \begin{aligned} \lambda_{j_1} + \lambda_{j_2}+ \lambda_{j_3}+ \lambda_{j_4} &= 0 \\ b_{j_1}\lambda_{j_1} + b_{j_2}\lambda_{j_2}+ b_{j_3}\lambda_{j_3}+ b_{j_4}\lambda_{j_4} &= 0 \\ c_{j_1}\lambda_{j_1} + c_{j_2}\lambda_{j_2}+ c_{j_3}\lambda_{j_3}+ c_{j_4}\lambda_{j_4} &= 0. \end{aligned}

Some of the $\lambda_{j_k}$ will be positive, some will be negative (some might be 0 – deal with that case separately). Assume for simplicity that $\lambda_{j_1}, \lambda_{j_2}$ are positive and $\lambda_{j_3}, \lambda_{j_4}$ are negative – the other cases being all similar. We claim that the line $\ell$ of equation

$\displaystyle \ell : \qquad (\lambda_{j_1} + \lambda_{j_2})x + (b_{j_1}\lambda_{j_1}+ b_{j_2} \lambda_{j_2})y + (c_{j_1}\lambda_{j_1}+ c_{j_2} \lambda_{j_2}) = 0 \ \ \ \ \ (1)$

intersects all $N+1$ rectangles of $\mathcal{R}$ at once.
Observe that the equation of $\ell$ can be rewritten in terms of $\lambda_{j_3}, \lambda_{j_4}$, namely

$\displaystyle (-\lambda_{j_3} + \lambda_{j_4})x + (-b_{j_3}\lambda_{j_3}- b_{j_4} \lambda_{j_4})y + (-c_{j_3}\lambda_{j_3}- c_{j_4} \lambda_{j_4}) = 0. \ \ \ \ \ (2)$

Now, let $j \in \{1, \ldots, N+1\}$ be the index of a rectangle in $\mathcal{R}$. $R_j$ intersects every line $\ell_{i}$ with $i \neq j$, so for every such $i$ we can find a point $p^{(j)}_i$ in (the interior of) $R_j$, of coordinates $(x^{(j)}_i, y^{(j)}_i)$, such that $p^{(j)}_i \in R_{j} \cap \ell_i$; in coordinate terms, for every $i \neq j$

$\displaystyle x^{(j)}_i + b_i y^{(j)}_i + c_i = 0.$

Now, the index $j$ cannot belong to both sets $\{j_1, j_2\}$, $\{j_3, j_4\}$ at once; let’s assume that $j$ does not belong to $\{j_1, j_2\}$. Consider then point $q^{(j)}$ given by the following convex combination of coordinates of $p^{(j)}_{j_1}$ and $p^{(j)}_{j_2}$ :

$\displaystyle q^{(j)} = \Big( \frac{\lambda_{j_1} x^{(j)}_{j_1}+ \lambda_{j_2} x^{(j)}_{j_2}}{\lambda_{j_1}+\lambda_{j_2}}, \frac{b_{j_1}\lambda_{j_1} y^{(j)}_{j_1}+ b_{j_2}\lambda_{j_2} y^{(j)}_{j_2}}{b_{j_1}\lambda_{j_1} + b_{j_2}\lambda_{j_2} }\Big).$

Notice how the weights have been chosen. Because the coordinates are convex combinations of the coordinates of two points in $R_j$, the point $q^{(j)}$ itself belongs to $R_j$ (however, they are convex combinations with distinct weights for the two coordinates; thus this is only true if the set is a rectangle, and not just a convex set more in general!). Moreover, it’s immediate to see by substitution that $q^{(j)}$ satisfies equation (1), and therefore $\ell$ intersects (the interior of) $R_j$. Repeat the argument for all $j$‘s to conclude (notice, if $j$ had belonged to $\{j_1, j_2\}$ we would have used $\lambda_{j_3},\lambda_{j_4}$ and equation (2) to reach the same conclusion). $\square$