yoyoflo wrote:

USJL wrote:

This problem is proposed by ltf0501and me!

Solution

Lemma 1. There exists a line separating the points such that the distances from the points to the line is at least $D/2N$ .
Proof
Up to a constant, we can interpret the maximum value of $d$ among all the choices of line as follows: every (open) strip of width $d$ that has points on both sides (outside the strip) contain at least one point. We will use this interpretation in the proof.

Lemma 2. There exists a positive absolute constant $c''$ such that
$\frac{1}{d^2}\leq c''D.$ Proof
Now by Lemma 1. we have $d\gtrsim D/N$ , and by Lemma 2. we have $d^2\gtrsim 1/D$ . Multiplying the two inequalities, we get that $d^3\gtrsim 1/N$ , which shows that $d\gtrsim N^{-1/3}$ .

Some interesting stories behind this problem

Really nice solution!! Although shouldn’t one say that D gets devided into at most n-1 Intervals with the projection (two points can map to same point) The argument still holds identically from there

Ah that's a really minor point. I guess it can be easily fixed by allowing intervals to have length zero.