Problem 834

We give the author's solution. In terms of $n$, we wish find the smallest integer $k$ for which $(0,1)^{2} \backslash S$ is always a union of $k$ open rectangles for every set $S \subset(0,1)^{2}$ of size $n$.
We claim the answer is $k=2 n+2$.
The lower bound is given by picking
$$S=\left\{\left(s_{1}, s_{1}\right),\left(s_{2}, s_{2}\right), \ldots,\left(s_{n}, s_{n}\right)\right\}$$
for some real numbers $00$. The four rectangles covering each of
$$\left(s_{1}-\varepsilon, s_{1}\right),\left(s_{1}, s_{1}-\varepsilon\right),\left(s_{n}+\varepsilon, s_{n}\right),\left(s_{n}, s_{n}+\varepsilon\right)$$
cannot cover any other points in $S^{\prime}$; all other rectangles can only cover at most 2 points in $S^{\prime}$, giving a bound of
$$k \geq 4+\frac{\left|S^{\prime}\right|-4}{2}=2 n+2 .$$

To prove that $2 n+2$ rectangles are sufficient, assume that the number of distinct $y$-coordinates is at least the number of distinct $x$-coordinates. Let
0=x_{0}0$ gives a total of
(m+n+2)+(n-m)=2 n+2
$$$$
rectangles.

We claim the answer is $k=2 n+2$. The lower bound is given by picking
$$S=\left\{\left(s_{1}, s_{1}\right),\left(s_{2}, s_{2}\right), \ldots,\left(s_{n}, s_{n}\right)\right\}$$
for some real numbers $0<s_1 < s_2 < \ldots < s_n$. The four rectangles covering each of
$$\left(s_{1}-\varepsilon, s_{1}\right),\left(s_{1}, s_{1}-\varepsilon\right),\left(s_{n}+\varepsilon, s_{n}\right),\left(s_{n}, s_{n}+\varepsilon\right)$$
cannot cover any other points in $S^{\prime}$; all other rectangles can only cover at most 2 points in $S^{\prime}$, giving a bound of
$$k \geq 4+\frac{\left|S^{\prime}\right|-4}{2}=2 n+2$$
!
To prove that $2 n+2$ rectangles are sufficient, assume that the number of distinct $y$-coordinates is at least the number of distinct $x$-coordinates. Let
$$0=x_{0}<x_{1}<\cdots<x_{m} \leq 1$$
be the distinct $x$-coordinates, and
$$0=y_{0}<y_{1}<\cdots<y_{n} \leq 1$$
be the distinct $y$-coordinates, where $m \leq n$. We can cover the points with the following rectangles:
- For each $i$ from $1$ to $m$, cover the points $(x_i, y_j)$ for $j=1, 2, \ldots, n$ with a rectangle of width $\varepsilon$ and height $y_{j+1} - y_{j-1}$.
- For each $j$ from $1$ to $n$, cover the points $(x_i, y_j)$ for $i=1, 2, \ldots, m$ with a rectangle of width $x_{i+1} - x_{i-1}$ and height $\varepsilon$.
- Cover the points $(0, y_j)$ for $j=1, 2, \ldots, n$ with a rectangle of width $\varepsilon$ and height $y_{j+1} - y_{j-1}$.
- Cover the points $(x_i, 0)$ for $i=1, 2, \ldots, m$ with a rectangle of width $x_{i+1} - x_{i-1}$ and height $\varepsilon$.

This gives a total of
$$(m+n+2)+(n-m)=2 n+2$$
rectangles.