How many points in the square

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 $x_{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{aligned} 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{aligned}$

which is a contradiction. Therefore, $\mu = \frac {1}{2n+2}$ , so we substitute $n=5$ to get the value of $\mu$ as $\frac{1}{12} \approx 0.083$ .

Whoa... I love this problem! (+1)

Here is a justification for $\frac{1}{12}$ . See Sharky's solution for a more complete explanation about why/how the construction is optimal...

Although I don't yet have a proof that $\frac{1}{12}$ (which leads to the answer of $13$ above) is the largest value for $\mu$ , I do have an example for which you can achieve it, where you distribute the points as follows:

• Four points forming a "tiny" box with the same orientation as $U$ around $(\frac{n}{6},\frac{1}{2})$ where $n$ ranges from $1$ to $5$ .

Or more explicity:

• $(\frac{n}{6}+\delta,\frac{1}{2}+\delta)$ where $n$ ranges from $1$ to $5$
• $(\frac{n}{6}+\delta,\frac{1}{2}-\delta)$ where $n$ ranges from $1$ to $5$
• $(\frac{n}{6}-\delta,\frac{1}{2}+\delta)$ where $n$ ranges from $1$ to $5$
• $(\frac{n}{6}-\delta,\frac{1}{2}-\delta)$ where $n$ ranges from $1$ to $5$

Let $\delta \rightarrow 0$