How can we divide a plane with $2n$ points into two equal halves with $n$ points each using a line?

  • 3
    $\begingroup$ en.wikipedia.org/wiki/Ham_sandwich_theorem (This is not a joke, but actually precisely a theorem that does what you want) $\endgroup$
    – Felix
    Jan 22, 2019 at 16:10
  • $\begingroup$ @Enkidu I think the article is too complex for a simple problem like this one $\endgroup$
    – Saša
    Jan 22, 2019 at 16:20

1 Answer 1


The usual construction is this: since there are only finitely many points, the collection of directions from one point to another is finite. Take any line with a slope which differs from all of those directions. Then no parallel translate of this line can go through $2$ of your points. Start to parallel translate your line toward the side that has more points. As you translate the count changes one at a time so eventually you reach parity.

  • $\begingroup$ Suppose that J is a minimal traveling-salesman path for the 2n points and suppose that J contains a square and suppose that there exists a diagonal of the square such that the line L containing that diagonal contains none of the 2n points. Does the line L bisect the set of 2n points? $\endgroup$
    – user584285
    Nov 28, 2020 at 16:50
  • $\begingroup$ I have never really thought about minimal salesman paths. Not sure what it means to say that one contains a square. Might be worth posting as a new question, but I suggest including a few examples to illustrate the phenomenon you have in mind. $\endgroup$
    – lulu
    Nov 28, 2020 at 16:55
  • $\begingroup$ Whether every Joran curve contains a square is a famous open problem. It is known as the 'inscribed square problem'. A salesman path, minimal or not, is a Jordan curve, and so the open problem applies to it. However, the Wikipedia article on this states that it is known to be true in certain cases, such as if the Jordan curve is piecewise smooth. I guess it's clear that a minimal salesman path will be piecewise smooth, and so we can drop that supposition from the question. $\endgroup$
    – user584285
    Nov 29, 2020 at 23:48

You must log in to answer this question.

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