TSTST 2026 Problem 9

In the plane, we say that a set of points $A = \{A_1, A_2, \dots, A_k\}$ demolishes a set of points $B = \{B_1, B_2, \dots, B_\ell\}$ if, for all points $P$,

$$PA_1 + PA_2 + \cdots + PA_k \geq PB_1 + PB_2 + \cdots + PB_\ell.$$

Let $S$ be a set of $n$ points in the plane. Show that we can partition $S$ into two sets $A$ and $B$ such that $A$ demolishes $B$ and $|A| \leq |B| + 100\sqrt{n}$.