2
$\begingroup$

Definition. If a some set of $n$ points of the plane can be divided into two subsets $\{ A_1, \; A_2, \; ..., \; A_k\}$ and $\{ B_1, \; B_2, \; ..., \; B_{n-k}\}$ so that there is a point $M$ of the plane such that $ MA_1+ MA_2+ ...+MA_k= MB_1+ MB_2+ ...+MB_{n-k} $, then we shall say that there exists a good partition of the set of these $n$ points of the plane.

a) Prove that for every set of $n \ge 2$ points of the plane there is at least one good partition.

b) Prove that if $n$ is even then for every set of $n \ge 2$ points of the plane there is at least one good partition such that both subsets of points contain $\frac{n}{2}$ points each.

My work. I solved the problem for cases when $n=2$ and $n=4$. If $n = 2$ then everything is easy: the point $M$ is an arbitrary point of the perpendicular bisector of a line segment $A_1B_1$. If $n = 4$ then we randomly denote four points by letters $A_1,\; A_2, \;B_1, \; B_2$. Let $a$ be a real number such that $a>A_1B_1+A_1B_2+A_1A_2$. We construct an ellipse $w_1$ with foci at points $A_1$ and $A_2$ and with semi-major axis $a$. Then all two points $ B_1, \; B_2$ are inside this ellipse. We construct an ellipse $w_2$ with foci at points $B_1$ and $B_2$ and with semi-major axis $a$. These ellipses $w_1$ and $w_2$ will intersect at two points. Let $M$ be a intersection point of ellipses $w_1$ and $w_2$. Then $ MA_1+ MA_2=2a= MB_1+ MB_2$. I have no idea how to solve the problem in general.

$\endgroup$

1 Answer 1

2
$\begingroup$

Let your points be $p_1, \ldots, p_n$. If $n$ is even, take a vector $v$ such that the dot products $p_i \cdot v$ are all distinct, sort your points according to these dot products, and take the least $n/2$ values for one subset ($A$) and the greatest $n/2$ for the other ($B$). Note that if $t$ is sufficiently large and positive, all points in $A$ are farther from $tv$ than are all points in $B$; the reverse is true for $-tv$. Use the Intermediate Value Theorem to show that you can take $M = t v$ for some real $t$.

EDIT: To clarify, the function to use the Intermediate Value Theorem on is the sum of distances from $tv$ to the points in $A$ minus the sum of distances from $tv$ to the points in $B$. It is easy to prove that this is continuous, using the fact that the sum or difference of continuous functions is continuous.

If $n$ is odd, let $A$ consist of $p_1$ and the $(n-1)/2$ closest points to $p_1$ (breaking ties arbitrarily), $B$ the farthest $(n-1)/2$. For $M = p_1$ the sum of distances to points in $A$ is $\le$ the sum of distances to points in $B$. For $M$ very far away the sum of distances to points in $A$ is greater. Again use the Intermediate Value Theorem.

$\endgroup$
1
  • $\begingroup$ Very nice proof of a) and b)! Thank you very much! $\endgroup$
    – Witold
    Commented Jun 19, 2019 at 12:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .