How can we divide a plane with $2n$ points into two equal halves with $n$ points each using a line?
$\begingroup$
$\endgroup$
2
-
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$– FelixJan 22, 2019 at 16:10
-
$\begingroup$ @Enkidu I think the article is too complex for a simple problem like this one $\endgroup$– SašaJan 22, 2019 at 16:20
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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$– user584285Nov 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$– luluNov 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$– user584285Nov 29, 2020 at 23:48