Let $n$ be a positive integer. Find the smallest positive integer $k$ such that for any set $S$ of $n$ points in the interior of the unit square, there exists a set of $k$ rectangles such that the following hold:
- The sides of each rectangle are parallel to the sides of the unit square.
- Each point in $S$ is not in the interior of any rectangle.
- Each point in the interior of the unit square but not in $S$ is in the interior of at least one of the $k$ rectangles.
(The interior of a polygon does not contain its boundary.)
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.