Given a positive integer $n$, determine the largest real number $\mu$ satisfying the following condition: for every set $C$ of $4n$ points in the interior of the unit square $U$, there exists a rectangle $T$ contained in $U$ such that $\bullet$ the sides of $T$ are parallel to the sides of $U$; $\bullet$ the interior of $T$ contains exactly one point of $C$; $\bullet$ the area of $T$ is at least $\mu$.
Problem
Source: RMM 2015 Problem 6
Tags: RMM, rectangle, combinatorial geometry, combinatorics, RMM 2015
01.03.2015 18:36
Looks like the answer is $\mu = 1/(2n+2)$. The maximality comes from the case in which $C$ is the set of points of the form $(1/2 \pm \epsilon, k/(n+1) \pm \epsilon)$, where $1 \le k \le n$ and $\epsilon > 0$ is small. Let $x_1 < \cdots < x_k$ be the possible $x$-coordinates of the points of $C$, and let $a_i$ be the number of points whose $x$-coordinate is $x_i$. Also, let $x_0 = 0, x_{k+1} = 1$. Suppose that for any such $T$ satisfying the first two conditions, the area of $T$ is less than $\mu = 1/(2n+2)$. For every $1 \le i \le k$, the region $x_{i-1} \le x \le x_{i+1}, 0\le y \le 1$ can be covered by $\lfloor a_i / 2 \rfloor + 1$ rectangles satisfying the first two conditions. (If $y_1 < \cdots < y_{a_i}$ are the $y$-coordinates then let the rectangles cover the range $y \in (0, y_2), (y_2, y_4), \cdots$ and $x \in (x_{i-1}, x_{i+1})$. It can be easily shown that each rectangle covers exactly one point.) Since the area of each rectangle is less than $\mu$, summing up the areas, we get $x_{i+1} - x_{i-1} < ( \lfloor a_i / 2 \rfloor + 1 ) \mu$. Now we do the same thing for the $x$-axis. For the sake of convenience, denote $f(x) = \lfloor x / 2 \rfloor + 1$. If $k = 2t+1$, then $$1 = (x_2 - 0) + (x_4 - x_2) + \cdots + (x_{2t} - x_{2t-2}) + (1- x_{2t}) < ( f(a_1) + f(a_3) + \cdots + f(a_{2t+1}) \mu$$ and $$ 1 < (x_2 - 0) + (x_3 - x_1) + (x_5 - x_3) + \cdots + (x_{2t+1} - x_{2t-1}) + (1 - x_{2t}) < (f(a_1) + f(a_2) + f(a_4) + \cdots + f(a_{2t}) + f(a_{2t+1})) \mu. $$ Adding these up, we obtain $$ 2 < ( 2 f(a_1) + f(a_2) + f(a_3) + \cdots + f(a_{k-1}) + 2 f(a_k)) \mu. $$ When $k = 2t$, adding $1 < ( f(a_1) + f(a_2) + f(a_4) + \cdots + f(a_{2t}) ) \mu $ and $1 < ( f(a_1) + f(a_3) + \cdots + f(a_{2t-1}) + f(a_{2t}))\mu$, we get the same inequality. Since $2 f(x) \le 2 ( x/2 + 1) = x+2$ and $ f(x) \le x$ for all integers $x \ge 1$, we have $$ 2 < (a_1 + 2 + a_2 + a_3 + \cdots + a_{k-1} + a_k + 2) \mu = 2,$$ which certainly is a contradiction.
13.04.2017 07:41
If you were trying small cases for \(n\) in the generalised case, you might notice that \(\mu = \frac {1}{2n+2}\) seems to work. Let's try and prove this. Let's first try to establish an upper bound on \(\mu\). We will prove \(\mu \leq \frac {1}{2n+2}\). Suppose \(\mu>\frac {1}{2n+2}\). Consider the \(n\) points \((\frac {1}{n+1}, \frac {1}{2}), (\frac {2}{n+1}, \frac {1}{2}), \ldots, (\frac {n}{n+1}, \frac {1}{2})\). Now split each of these points into four points by adding \((\pm \epsilon, \pm \epsilon)\) to each point. A rectangle that contains exactly one of these has height less than \(\frac {1}{2} + \epsilon\) and base less than \(\frac {1}{n+1} + \epsilon\). Thus, such a rectangle has area less than \((\frac {1}{n+1} + \epsilon)(\frac {1}{2} + \epsilon) < \mu\) if \(\epsilon\) is small enough. Thus, we have a contradiction. Hence, \(\mu \leq \frac {1}{2n+2}\). We shall now prove that \(\mu = \frac {1}{2n+2}\). First, though, let us solve what amounts to the one-dimensional version of the problem as in the following lemma. **Lemma.** Let \(t_1 < t_2 < ... < t_k\) be points in the open interval \((0, 1)\). Then there exists an open sub-interval \(I \subseteq (0, 1)\) of length \(\frac {1}{\left \lfloor \frac{k}{2} \right \rfloor+1}\) that contains exactly one of the \(t_i\). **Proof.** If \(k=2h+1\) is odd, consider the following \(h+1\) intervals. \[(0, t_2), (t_2, t_4), (t_4, t_6), \ldots, (t_{2h-2}, t_{2h}), (t_{2h}, 1)\] Each such interval contains exactly one \(t_i\). Moreover, the sum of the lengths of those intervals is 1. Hence, one of them has length at leat \(\frac {1}{h+1} = \frac {1}{\left \lfloor \frac{k}{2} \right \rfloor+1}\), as required. If \(k=2h\) is even, consider the following \(h+1\) intervals. \[(0, t_2), (t_2, t_4), (t_4, t_6), \ldots, (t_{2h-2}, t_{2h}), (t_{2h-1}, 1)\] Each such interval contains exactly one \(t_i\). Moreover, the sum of their lengths is \(1+t_{2h}-t_{2h-1}\), which is more than 1. Hence, one of them has length greater than \(\frac {1}{h+1} = \frac {1}{\left \lfloor \frac{k}{2} \right \rfloor+1}\), as required. \(_{\square}\) Second, we now solve the 2D version of this problem. Let \(x_1 < x_2 < ... < x_k\) denote the set of \(x\)-coordinates of the points in \(C\). Note that if all \(x\)-coordinates of points in \(C\) are different, then \(k=4n\), otherwise \(k<4n\). We also define \(x_0 = 0\) and \(a_{k+1}=1\), so that \(x_0 < x_1 < \ldots < x_k < x_{k+1}\). For \(i = 0, 1, 2, \ldots, k, k+1\), let \(l_i\) be the vertical line through \(x_i\), and for \(i=1, 2, ..., k\), let \(m_i = |C \cap l_i|\). Note that \(\sum_{i=1}^k m_i = 4n\). Applying the lemma along line \(l_i\), there is a vertical interval \(I\) of length \(\frac {1}{\left \lfloor \frac {m_i}{2} \right \rfloor + 1}\) that contains exactly one point of \(C \cap l_i\). Thus the rectangle bounded by the horizontal projections of \(I\) onto \(l_{i-1}\) and \(l_{i+1}\) contains exactly one point of \(C\). The area of this rectangle is \(\frac {x_{i+1} - x_{i-1}}{\left \lfloor \frac {m_i}{2} \right \rfloor + 1}\), and we have one such rectangle for each \(i\). Suppose, for the sake of contradiction, that all such areas are less than \(\frac {1}{2n+2}\). It follows that \[x_{i+1} - x_{i-1} < \dfrac {\left \lfloor \frac {m_i}{2} \right \rfloor +1}{2n+2}, \quad \text{for } i=1, 2, \ldots, k. \quad (1)\] However, \[(x_{k+1} - x_k) + (x_1 - x_0) + \displaystyle \sum_{i=1}^k (x_{i+1} - x_{i-1}) = 2(x_{k+1} - x_0) = 2. \quad (2)\] We know \(x_{k+1} - x_k < x_{k+1} - x_{k-1}\), and \(x_1 - x_0 < x_2 - x_0\). Using these and \((1)\) and \((2)\), we have \begin{align*} 4n+4 &< \left (\left \lfloor \dfrac {m_k}{2} \right \rfloor + 1 \right ) + \left (\left \lfloor \dfrac {m_1}{2} \right \rfloor + 1 \right ) + \displaystyle \sum_{i=1}^k \left (\left \lfloor \dfrac {m_i}{2} \right \rfloor + 1 \right )\\ &= 2 \left \lfloor \dfrac {m_1}{2} \right \rfloor + 2 \left \lfloor \dfrac {m_k}{2} \right \rfloor + 4 + \displaystyle \sum_{i=2}^{k-1} \left (\left \lfloor \dfrac {m_i}{2} \right \rfloor + 1 \right )\\ &\leq m_1 + m_2 + 4 + \displaystyle \sum_{i=2}^{k-1} m_i \quad (\text{since } 2 \left \lfloor \frac {x}{2} \right \rfloor \leq x, \text{ and } \left \lfloor \frac {m_i}{2} \right \rfloor \leq m_i - 1 \text{ for } m_i \in \mathbb{N}^{+})\\ &= 4n+4, \end{align*} which is a contradiction. Therefore, \(\mu = \frac {1}{2n+2}\), so we're done.
06.02.2024 06:35
The answer is $\frac{1}{2(n+1)}$. A construction showing that this is maximal is letting $C$ contain points of the form $\left(\frac{1}{2}\pm \varepsilon,\frac{k}{n+1} \pm \varepsilon\right)$ for $1 \leq k \leq n$ and some infinitesimal $\varepsilon>0$. We prove the following claim, which is essentially the one-dimensional version of this problem. Claim: For $k \geq 1$, let $p_1<\ldots<p_k$ be points in $(0,1)$. Then there exists some open subinterval of $(0,1)$ that contains exactly one point and has length at least $\frac{1}{\lfloor k/2\rfloor+1}$. Proof: Let $d_i=p_{i+1}-p_i$ for each $i$, and define $d_0=p_1$ and $d_k=1-p_k$ and $d_0+\cdots+d_k=1$. In other words, the $d_i$ are "gaps" between points. It suffices to exhibit some $0 \leq i<k$ with $d_i+d_{i+1} \geq \frac{1}{\lfloor k/2\rfloor+1}$. Indeed, if $k$ is even then we have $$1\leq \underbrace{(d_0+d_1)+(d_2+d_3)+\cdots+(d_{k-2}+d_{k-1})+(d_{k-1}+d_k)}_{k/2+1\text{ terms}},$$and if $k$ is odd we have $$1=\underbrace{(d_0+d_1)+(d_2+d_3)+\cdots+(d_{k-1}+d_k)}_{(k+1)/2\text{ terms}},$$so by expectation the result follows. $\blacksquare$ Returning to the two-dimensional case, group the points in an arbitrary choice of $C$ by $x$-coordinate. Suppose we have $k$ groups, and let $a_0,\ldots,a_k$ denote the "gaps" between groups' $x$-coordinates (so $a_0$ is simply the coordinate of the leftmost group, etc.), so $a_0+\cdots+a_k=1$. Suppose that for $1 \leq i \leq k$, the $i$-th group contains $b_i\geq 1$ points, so $b_1+\cdots+b_k=4n$. By the above claim, for each $i$ we can find a working rectangle with area at least $\frac{a_{i-1}+a_i}{\lfloor b_i/2\rfloor+1}$, which contains exactly one point in the $i$-th group, having width $a_{i-1}+a_i$ and height at least $\frac{1}{\lfloor b_i/2\rfloor+1}$. Thus, suppose that for all $i$ we have $$\frac{a_{i-1}+a_i}{\lfloor b_i/2\rfloor+1}<\frac{1}{2(n+1)} \iff a_{i-1}+a_i<\frac{\lfloor b_i/2\rfloor+1}{2(n+1)}.$$Summing over all $i$, we have $$2-a_0-a_k<\frac{1}{2(n+1)}\sum_{i=1}^k (\lfloor b_i/2\rfloor+1).$$But we also have $a_0<\frac{\lfloor b_1/2\rfloor+1}{2(n+1)}$ and $a_k<\frac{\lfloor b_k/2\rfloor+1}{2(n+1)}$, so \begin{align*} 2&<\frac{1}{2(n+1)}\left(2(\lfloor b_1/2\rfloor+1)+2(\lfloor b_k/2\rfloor+1)+\sum_{i=2}^{k-1} (\lfloor b_i/2\rfloor+1)\right)\\ 4n+4&<(b_1+2)+(b_k+2)+\sum_{i=2}^{k-1} b_i, \end{align*}where $2(\lfloor x/2\rfloor+1) \leq x+2$ is obvious, and $\lfloor x/2\rfloor+1 \leq x$ is clearly true for $x \geq 1$. But the RHS above equals $(b_1+\cdots+b_k)+4=4n+4$, so we arrive at a contradiction. $\blacksquare$