, 2015

The required maximum is $1/(2n+2)$. To show that the condition in the statement is not met if $\mu > 1/(2n+2)$, let $U = (0,1) \times (0,1)$, choose a small enough positive $\varepsilon$, and consider the configuration $C$ consisting of the $n$ four-element clusters of points $(i/(n+1) \pm \varepsilon) \times (1/2 \pm \varepsilon)$, $i = 1, \dots, n$, the four possible sign combinations being considered for each $i$. Clearly, every open rectangle in $U$, whose sides are parallel to those of $U$, which contains exactly one point of $C$, has area at most $(1/(n+1) + \varepsilon)(1/2 + \varepsilon) < \mu$ if $\varepsilon$ is small enough.

We now show that, given a finite configuration $C$ of points in an open unit square $U$, there always exists an open rectangle in $U$, whose sides are parallel to those of $U$, which contains exactly one point of $C$, and has an area greater than or equal to $\mu_0 = 2/(|C| + 4)$.

To prove this, usage will be made of the following two lemmas whose proofs are left at the end of the solution.

Lemma 1. Let $k$ be a positive integer, and let $\lambda < 1/(|k/2| + 1)$ be a positive real number. If $t_1, \dots, t_k$ are pairwise distinct points in the open unit interval $(0,1)$, then some $t_i$ is isolated from the other $t_j$ by an open subinterval of $(0,1)$ whose length is greater than or equal to $\lambda$.

Lemma 2. Given an integer $k \ge 2$ and positive integers $m_1, \dots, m_k$,
$$\lfloor m_1/2 \rfloor + \sum_{i=1}^{k} \lfloor m_i/2 \rfloor + \lfloor m_k/2 \rfloor \le \sum_{i=1}^{k} m_i - k + 2.$$

Back to the problem, let $U = (0,1) \times (0,1)$, project $C$ orthogonally on the $x$-axis to obtain the points $x_1 < \dots < x_k$ in the open unit interval $(0,1)$, let $\ell_i$ be the vertical through $x_i$, and let $m_i = |C \cap \ell_i|$, $i = 1, \dots, k$.

Setting $x_0 = 0$ and $x_{k+1} = 1$, assume that $x_{i+1} - x_{i-1} > (\lfloor m_i/2 \rfloor + 1)\mu_0$ for some index $i$, and apply Lemma 1 to isolate one of the points in $C \cap \ell_i$ from the other ones by an open subinterval $x_i \times J$ of $x_i \times (0,1)$ whose length is greater than or equal to $\mu_0/(x_{i+1} - x_{i-1})$. Consequently, $(x_{i-1}, x_{i+1}) \times J$ is an open rectangle in $U$, whose sides are parallel to those of $U$, which contains exactly one point of $C$ and has an area greater than or equal to $\mu_0$.

Next, we rule out the case $x_{i+1} - x_{i-1} \le (\lfloor m_i/2 \rfloor + 1)\mu_0$ for all indices $i$. If this were the case, notice that necessarily $k > 1$; also, $x_1 - x_0 < x_2 - x_0 \le (\lfloor m_1/2 \rfloor + 1)\mu_0$ and $x_{k+1} - x_k < x_{k+1} - x_{k-1} \le (\lfloor m_k/2 \rfloor + 1)\mu_0$. With reference to Lemma 2, write
$$\begin{align*} 2 = 2(x_{k+1} - x_0) &= (x_1 - x_0) + \sum_{i=1}^{k} (x_{i+1} - x_{i-1}) + (x_{k+1} - x_k) \\ &< \left( \left( \lfloor m_1/2 \rfloor + 1 \right) + \sum_{i=1}^{k} \left( \lfloor m_i/2 \rfloor + 1 \right) + \left( \lfloor m_k/2 \rfloor + 1 \right) \right) \cdot \mu_0 \\ &\le \left( \sum_{i=1}^{k} m_i + 4 \right) \mu_0 = (|C| + 4)\mu_0 = 2, \end{align*}$$
and thereby reach a contradiction.

Finally, we prove the two lemmas.

Proof of Lemma 1. Suppose, if possible, that no $t_i$ is isolated from the other $t_j$ by an open subinterval of $(0, 1)$ whose length is greater than or equal to $\lambda$. Without loss of generality, we may (and will) assume that $0 = t_0 < t_1 < \dots < t_k < t_{k+1} = 1$. Since the open interval $(t_{i-1}, t_{i+1})$ isolates $t_i$ from the other $t_j$, its length, $t_{i+1} - t_{i-1}$, is less than $\lambda$. Consequently, if $k$ is odd, then $1 = \sum_{i=0}^{(k-1)/2} (t_{2i+2} - t_{2i}) < \lambda(1 + (k-1)/2) < 1$; and if $k$ is even, then $1 < 1 + t_k - t_{k-1} = \sum_{i=0}^{k/2-1} (t_{2i+2} - t_{2i}) + (t_{k+1} - t_{k-1}) < \lambda(1 + k/2) < 1$. A contradiction in either case.

Proof of Lemma 2. Let $I_0$, respectively $I_1$, be the set of all indices $i$ in the range $2, \dots, k-1$ such that $m_i$ is even, respectively odd. Clearly, $I_0$ and $I_1$ form a partition of that range. Since $m_i \ge 2$ if $i$ is in $I_0$, and $m_i \ge 1$ if $i$ is in $I_1$ (recall that the $m_i$ are positive integers), $\sum_{i=2}^{k-1} m_i = \sum_{i \in I_0} m_i + \sum_{i \in I_1} m_i \ge 2|I_0| + |I_1| = 2(k-2) - |I_1|$, or $|I_1| \ge 2(k-2) - \sum_{i=2}^{k-1} m_i$. Consequently,
$$\begin{align*} \lfloor m_1/2 \rfloor + \sum_{i=1}^{k} \lfloor m_i/2 \rfloor + \lfloor m_k/2 \rfloor &\le m_1 + \left( \sum_{i=2}^{k-1} m_i/2 - |I_1|/2 \right) + m_k \\ &\le m_1 + \left( \sum_{i=2}^{k-1} m_i/2 - (k-2) + \sum_{i=2}^{k-1} m_i/2 \right) + m_k \\ &= \sum_{i=1}^{k} m_i - k + 2. \end{align*}$$